这题不难~但Bug找了很久,发现~~if后面加了个分号~~汗
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> using namespace std; int parent[105]; int count1; struct node { int u;int v; int w; node():u(0),v(0),w(0){} }; int find1(int i) { /*if(i!=parent[i]) //这个是路径压缩 parent[i]=find1(parent[i]); return parent[i]; */ while(i!=parent[i]) i=parent[i]; return i; } int merge(int i,int j) { i=find1(i); j=find1(j); if(i!=j) { parent[i]=j; return 1; } return 0; } bool cmp(node lhs,node rhs) { return lhs.w<rhs.w; } void init(int m) { count1=0; int i; for(i=0;i<=m;i++) parent[i]=i; } int main() { int n,m; while(scanf("%d%d",&n,&m),n!=0) { node map[105]; init(m); int i; for(i=0;i<n;i++) scanf("%d%d%d",&map[i].u,&map[i].v,&map[i].w); sort(map,map+n,cmp); int sum=0; for(i=0;i<n;i++) { if(merge(map[i].u,map[i].v)) { sum=sum+map[i].w; } } for(i=1;i<=m;i++) { if(parent[i]==i) count1++; } if(count1==1) { printf("%d\n",sum); } else printf("?\n"); } return 0; }