vijos1070 新年趣事之游戏 - 次小生成树

传送门

题目大意：

求原图的最小生成树，和次小生成树。

题目分析：

kruskals求mst（\(O(mlogm)\)）
考虑次小生成树暴力的做法，因为次小生成树总是由最小生成树删掉一条边并添加一条边得到的，所以可以枚举最小生成树上的每一条边删去，再重新求一遍mst。(\(O(m^2logm)\))
下面的题解来自转载：(\(O(n^2(求最大权值) + mlogm(求最小生成树) + m(求次小))\))

code

#include<bits/stdc++.h>
using namespace std;
const int N = 550, M = 150050, OO = 0x3f3f3f3f;
int n, ans, m;
struct node{int x, y, dis;inline bool operator < (const node &b) const{return dis < b.dis;}
}edge[M];
int d[N][N];
bool vst[N], used[M];
namespace mst{int ecnt, adj[N], nxt[M << 1], go[M << 1], len[M << 1];inline void addEdge(int u, int v, int c){nxt[++ecnt] = adj[u], adj[u] = ecnt, go[ecnt] = v, len[ecnt] = c;nxt[++ecnt] = adj[v], adj[v] = ecnt, go[ecnt] = u, len[ecnt] = c;}int anc[N];inline int getAnc(int x){return x == anc[x] ? x : (anc[x] = getAnc(anc[x]));}inline int kruskals(){int ret = 0;sort(edge + 1, edge + m + 1);for(int i = 1; i <= m; i++){int fx =  getAnc(edge[i].x), fy = getAnc(edge[i].y);if(fx != fy) anc[fx] = fy, ret += edge[i].dis, addEdge(edge[i].x, edge[i].y, edge[i].dis), used[i] = true;}return ret;}inline void dfs(int now, int u, int f, int mx){d[now][u] = d[u][now] = mx;for(int e = adj[u]; e; e = nxt[e]){int v = go[e];if(v == f) continue;dfs(now, v, u, max(mx, len[e]));}}
} int main(){scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++) mst::anc[i] = i;for(int i = 1; i <= m; i++){int x, y, c; scanf("%d%d%d", &x, &y, &c);edge[i] = (node){x, y, c};}ans = mst::kruskals();if(n - 1 == mst::ecnt / 2) printf("Cost: %d\n", ans);else printf("Cost: -1\nCost: -1\n");int ans1 = OO;for(int i = 1; i <= n; i++)mst::dfs(i, i, 0, 0);for(int i = 1; i <= m; i++){if(used[i]) continue;int x = edge[i].x, y = edge[i].y;ans1 = min(ans1, ans - d[x][y] + edge[i].dis);}if(ans1 != OO) printf("Cost: %d", ans1);else printf("Cost: -1");return 0;
}