无向连通图（无重边），判断最小生成树是否唯一，若唯一求边权和。
分析生成树的生成过程，只有一个圈内出现权值相同的边才会出现权值和相等但“异构”的生成树。（并不一定是最小生成树）
分析贪心策略求最小生成树的过程（贪心地选最短的边来扩充已加入生成树的顶点集合U），发现只有当出现“U中两个不同的点到V-U中同一点的距离同时为当前最短边”时，才会出现“异构”的最小生成树。
上图为kruscal和prim生成过程中可能遇到的相等边的情况，红色和蓝色的为权值相等的边。
可以看到kruscal由于事先将所有边按权值排序，所以在构造MST的过程中，当发现权值相同的边时，需要遍历之前遇到过的所有相同权值的边来判断是否发生“争抢同一点”的情况，若发现即可判定存在“异构”最小生成树。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 const int MAX_N=105; 6 const int MAX_M=5005; 7 8 int par[MAX_N]; 9 void init() 10 { 11 memset(par,-1,sizeof(par)); 12 } 13 int find(int x) 14 { 15 if(par[x]==-1) return x; 16 return par[x]=find(par[x]); 17 } 18 void unite(int x,int y) 19 { 20 x=find(x); 21 y=find(y); 22 if(x!=y) par[x]=y; 23 } 24 bool same(int x,int y) 25 { 26 return find(x)==find(y); 27 } 28 29 int t; 30 int n,m; 31 struct Edge 32 { 33 int u,v,w; 34 }e[MAX_M]; 35 36 bool cmp(Edge e1,Edge e2) 37 { 38 return e1.w<e2.w; 39 } 40 41 bool inter(Edge e1,Edge e2) 42 { 43 if(e1.u==e2.u||e1.u==e2.v||e1.v==e2.u||e1.v==e2.v) return true; 44 else return false; 45 } 46 47 int kruscal() 48 { 49 int ans=0; 50 init(); 51 ans+=e[0].w; 52 unite(e[0].u,e[0].v); 53 int cur_w=e[0].w; 54 for(int i=1;i<m;i++) 55 { 56 if(same(e[i].u,e[i].v)) 57 { 58 for(int j=i-1;e[j].w==e[i].w;j--) 59 { 60 if(inter(e[i],e[j]))//判两条边有无交点 61 { 62 ans=-1; 63 break; 64 } 65 } 66 }else 67 { 68 unite(e[i].u,e[i].v); 69 ans+=e[i].w; 70 cur_w=e[i].w; 71 } 72 } 73 return ans; 74 } 75 76 int main() 77 { 78 freopen("1679.txt","r",stdin); 79 scanf("%d",&t); 80 while(t--) 81 { 82 scanf("%d%d",&n,&m); 83 for(int i=0;i<m;i++) 84 { 85 scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w); 86 } 87 if(n==1) {printf("0\n"); continue;} 88 sort(e,e+m,cmp); 89 int ans=kruscal(); 90 if(ans==-1) 91 printf("Not Unique!\n"); 92 else printf("%d\n",ans); 93 } 94 return 0; 95 }
而prim由于每次都选连结U和V-U的边，所以不会遇到kruscal那样蓝色的可能误判的边（我开始就WA在这里），因此只需在加入一个新点更新其他点的mincost时判断有没有和mincost值相等的另一条边的即可。
1 #include <cstdio> 2 #include <cstring> 3 #include <vector> 4 #include <queue> 5 using namespace std; 6 const int MAX_N=105; 7 const int MAX_M=5005; 8 const int INF=100000; 9 typedef pair<int,int> P;//cost,to 10 struct Edge 11 { 12 int to,cost; 13 Edge(){} 14 Edge(int tt,int cc):to(tt),cost(cc){} 15 }; 16 int t; 17 int n,m; 18 vector<Edge> G[MAX_N]; 19 int vis[MAX_N]; 20 int mincost[MAX_N]; 21 22 int prim() 23 { 24 int ans=0; 25 int flag=0; 26 priority_queue<P,vector<P>,greater<P> > que; 27 memset(vis,0,sizeof(vis)); 28 for(int i=1;i<=n;i++) mincost[i]=INF; 29 que.push(P(0,1)); 30 mincost[1]=0; 31 while(!que.empty()) 32 { 33 P p=que.top(); 34 que.pop(); 35 int v=p.second; 36 if(vis[v]||mincost[v]<p.first) continue; 37 vis[v]=1; 38 mincost[v]=p.first; 39 ans+=mincost[v]; 40 for(int i=0;i<G[v].size();i++) 41 { 42 int u=G[v][i].to; 43 if(!vis[u]) 44 { 45 if(mincost[u]>G[v][i].cost&&G[v][i].cost<INF) 46 { 47 mincost[u]=G[v][i].cost; 48 que.push(P(mincost[u],u)); 49 }else if(mincost[u]==G[v][i].cost)//存在到达点u权值相等且都为最小值的边 50 { 51 flag=1; 52 break; 53 } 54 } 55 } 56 if(flag) break; 57 } 58 if(flag) ans=-1; 59 return ans; 60 } 61 int main() 62 { 63 freopen("1679.txt","r",stdin); 64 scanf("%d",&t); 65 while(t--) 66 { 67 scanf("%d%d",&n,&m); 68 for(int i=1;i<=n;i++) G[i].clear(); 69 for(int i=0;i<m;i++) 70 { 71 int u,v,w; 72 scanf("%d%d%d",&u,&v,&w); 73 G[u].push_back(Edge(v,w)); 74 G[v].push_back(Edge(u,w)); 75 } 76 if(n==1) {printf("0\n"); continue;} 77 int ans=prim(); 78 if(ans==-1) 79 printf("Not Unique!\n"); 80 else printf("%d\n",ans); 81 } 82 return 0; 83 }
