?
最近略忙,就不寫題意思路什么的,直接上代碼。
#include<stdio.h> #include<stdlib.h> struct edge { int u,v,w,flag; }p[4952]; int n,m; int f[101]; int used[101]; int cmp(const void*aa,const void*bb) { return ((struct edge*)aa)->w-((struct edge*)bb)->w; } int find(int x) { return f[x]==x?x:(f[x]=find(f[x])); } int Kruskal() { int sum=0,i,x,y,t=0; for(i=0;i<m;i++) { x=find(p[i].u); y=find(p[i].v); if(x!=y) { f[x]=y; sum+=p[i].w; used[t]=i; t++; if(t==n-1) break; } } return sum; } int reKruskal() { int sum=0,i,x,y,t=0; for(i=0;i<m;i++) { x=find(p[i].u); y=find(p[i].v); if(x!=y&&!p[i].flag) { f[x]=y; sum+=p[i].w; t++; if(t==n-1) break; } } return sum; } int main() { //freopen("12.3.4.input.txt","r",stdin); int t,i,j,ans,tans,k,pt=0; scanf("%d",&t); for(i=0;i<t;i++) { scanf("%d %d",&n,&m); for(j=1;j<=n;j++) f[j]=j; for(j=0;j<n;j++) used[j]=-1; for(j=0;j<m;j++) { scanf("%d %d %d",&p[j].u,&p[j].v,&p[j].w); p[j].flag=0; } qsort(p,m,sizeof(p[0]),cmp); ans=Kruskal(); pt=0; for(j=0;j<n-1;j++) { p[used[j]].flag=1; for(k=1;k<=n;k++) f[k]=k; tans=reKruskal(); p[used[j]].flag=0; if(ans==tans&&ans!=0) { pt=1; break; } } if(pt) printf("Not Unique!\n"); else printf("%d\n",ans); } return 0; }
?
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
