解题报告:最小生成树是否唯一判断方法
(1)图中每条边,扫描其他边,如果存在权值相同的边,则对其边标记
(2)用kruskal或prim算法求最小生成树的权值
(3)得到最小生成树,如果该最小生成树不包含标记的边,则最小生成树唯一,如果包含了标记的边,则依次去掉标记的边,再求最小生成树,如果求得的最小生成树与原最小生成树的权值相同,则最小生成树不唯一
code:
#include<cstdio> #include<cstring> #include<algorithm> #define maxn 105 #define INF 0x7fffffff using namespace std; struct node { int u, v, w; int equal; int used; int del; }edge[maxn*maxn]; int parent[maxn]; int n, m; bool first; bool cmp( const node &a, const node &b) { return a.w < b.w; } void UFset( ) { for(int i = 0; i <= n; i++) parent[i] = -1; } int Find( int x ) { int s ; for( s = x; parent[s] >= 0; s = parent[s] ); while(s != x ) { int temp = parent[x]; parent[x] = s; x = temp; } return s; } void Union( int R1, int R2 ) { int r1 = Find(R1); int r2 = Find(R2); int temp = parent[r1] + parent[r2]; if(parent[r1] > parent[r2]) { parent[r1] = r2; parent[r2] = temp; } else { parent[r2] = r1; parent[r1] = temp; } } int kruskal( ) { UFset( ); int i, j; int u, v; int sumweight = 0, num = 0; for( i = 0; i <m; i++ ) { if(edge[i].del == 1 ) continue; u = edge[i].u; v = edge[i].v; if( Find(u) != Find(v) ) { sumweight += edge[i].w; num++; Union( u, v ); if( first ) edge[i].used = 1; } if( num >= n-1 ) break; } return sumweight; } int main( ) { int T, u, v, w, j, i; scanf("%d",&T); while( T-- ) { memset(edge, 0, sizeof(edge) ); scanf("%d%d", &n, &m); for( i = 0; i < m; i++ ) { scanf("%d%d%d", &u, &v, &w); edge[i].u = u; edge[i].v = v; edge[i].w = w; } for(i = 0; i < m; i++ ) { for( j = 0; j < m; j++ ) { if( i == j ) continue; if( edge[i].w == edge[j].w ) edge[j].equal = 1; } } sort(edge, edge + m, cmp); first = true; int ans1 = kruskal( ); int ans2; first = false; for( i = 0; i < m; i++ ) { if(edge[i].used && edge[i].equal ) { edge[i].del = 1; ans2 = kruskal( ); if(ans1 == ans2 ) { printf("Not Unique!\n"); break; } edge[i].del = 0; } } if( i >= m ) printf("%d\n", ans1); } return 0; }
相关推荐
先利用prim算法求出最小生成树,然后通过往MST里加边来判断新生成的最小生成树是否具有最小的权值,POJ上The Unique MST(1679)题是要求判断最小生成树是否唯一,此题其实根本不用这样做,但是为了练习球次小生成树...
NULL 博文链接:https://200830740306.iteye.com/blog/603493
NULL 博文链接:https://128kj.iteye.com/blog/1705139
NULL 博文链接:https://128kj.iteye.com/blog/1704752
最小度限制生成树的求法也不是很难,先把度被限制的那个点(s点)去掉,求一次MST,然后把s到各个连通分量的最小权值的边加上,然后继续加边看看能否使生成树权减小(详见解题报告)。
poj 1611 The Suspects 代码 并查集的应用
NULL 博文链接:https://128kj.iteye.com/blog/1707218
北大POJ1027-The Same Game 解题报告+AC代码
度限制最小生成树代码 摘自POJ1639代码
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ1163-The Triangle 解题报告+AC代码
北大POJ1163-The Triangle
poj 1611 The Suspects.md
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 3191 The Moronic Cowmpouter.md
poj 1989 The Cow Lineup.md
poj 3260 The Fewest Coins.md
poj 3901 The Computer Game.md
poj2516代码最小费用最大流
北大POJ2151-Check the difficulty of problems 解题报告+AC代码