本文主要是介绍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; }
转载于:https://www.cnblogs.com/CzYoL/p/7732091.html
这篇关于vijos1070 新年趣事之游戏 - 次小生成树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
