C語言源碼： [cpp] #include<stdio.h> #include<stdlib.h> #define maxsize 110 typedef struct edge { int a,b; int weight; }edge; edge E[maxsize]; int T[maxsize]; int findroot(int x) { int temp; if(T[x]==-1) return x; else { temp=findroot(T[x]); T[x]=temp; return temp; } } int cmp(const void *a,const void *b) { edge *aa=(edge *)a; edge *bb=(edge *)b; return aa->weight-bb->weight; } int main() { int n,m,weight,i,num,roota,rootb; scanf("%d %d",&n,&m); while(n) { for(i=0;i<n;i++) scanf("%d %d %d",&E[i].a,&E[i].b,&E[i].weight); qsort(E,n,sizeof(E[0]),cmp); for(i=1;i<=m;i++) T[i]=-1; weight=0; num=0; for(i=0;i<n;i++) { roota=findroot(E[i].a); rootb=findroot(E[i].b); if(roota!=rootb) { T[rootb]=roota; weight+=E[i].weight; } } for(i=1;i<=m;i++) if(T[i]==-1) num++; if(num>1) printf("?\n"); else printf("%d\n",weight); scanf("%d %d",&n,&m); } }
