#include #include #include using namespace std; struct Edge{ int from; int to; int price; }; const int MAXN =100; Edge edge[MAXN*MAXN]; int father[MAXN]; int height[MAXN]; void Initial(int n){ for(int i=0;i<n;i++){ father[i]=i; height[i]=0; } return; } int Find(int x){ if(x!=father[x]){ father[x]=Find(father[x]); } return father[x]; } void Union(int x,int y){ int rootx =Find(x); int rooty=Find(y); if(rootx!= rooty){ if(height[rootx] > height[rooty]){ father[rooty]=rootx; }else if(height[rootx] < height[rooty]){ father[rootx]=rooty; }else{ father[rooty] =rootx; height[rootx]++; } } return; } bool compare(const Edge&a,const Edge&b){ return a.price<b.price; } void Kruskal(int n,int m){ Initial(n); sort(edge,edge+m,compare); int total_length=0; int count=0;//计数器 for(int i=0;i<m;i++){ Edge cur=edge[i]; if(Find(cur.from)!=Find(cur.to)){ count++; total_length +=cur.price; Union(cur.from,cur.to); } if(count == n-1)break; } if(count==n-1){ cout<<total_length<<endl; return; }else{ cout<<"?"<<endl; return; } } int main(){ int n,m; while(scanf("%d %d",&m,&n) != EOF){ if(m==0){ break; } for(int i=0;i<m;i++){ scanf("%d %d %d",&edge[i].from,&edge[i].to,&edge[i].price); } Kruskal(n,m); } return 0; }注意问题中n和m的意思即可，注意调换；