poj 1679 The Unique MST （最小生成树是不是唯一 ）

poj 1679 The Unique MST （最小生成树是否唯一 ）

题目链接：poj 1679 The Unique MST

?

解题报告：最小生成树是否唯一判断方法

（1）图中每条边，扫描其他边，如果存在权值相同的边，则对其边标记

（2）用kruskal或prim算法求最小生成树的权值

（3）得到最小生成树，如果该最小生成树不包含标记的边，则最小生成树唯一，如果包含了标记的边，则依次去掉标记的边，再求最小生成树，如果求得的最小生成树与原最小生成树的权值相同，则最小生成树不唯一

?

code:

#include<cstdio>#include<cstring>#include<algorithm>#define maxn 105#define INF 0x7fffffffusing 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;}

?