第一次接触最小生成树,也不知道自己写的这个算不上,只知道自己wa了好多次,都是因为一些细节。。。
#include<stdio.h> #include<algorithm> using namespace std; struct road { int x; int y; int mon; }p[10002]; int city[10002]; int cmp(struct road a,struct road b) { return a.mon<b.mon; } int find(int a) { return a==city[a]?a:find(city[a]); } int main() { int n,m; while(scanf("%d%d",&n,&m),n) { for(int i=0;i<n;i++) scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].mon); for(int i=1;i<=m;i++) city[i]=i; sort(p,p+n,cmp); int a,b,sum=1,res=0; for(int i=0;i<n;i++) { a=find(p[i].x); b=find(p[i].y); if(a!=b) { sum++; res+=p[i].mon; city[a]=b; } } if(sum==m) printf("%d\n",res); else printf("?\n"); } return 0; }