拉牛上山采菊花 拉牛上山采菊花
搬砖路上
关注数: 997 粉丝数: 696 发帖数: 3,391 关注贴吧数: 315
求救并查集问题 #include<stdio.h> #define N 101 int a[N]; int x[N],y[N],q[N]; int sum; int find(int x) { int r=x; while(a[r]!=r) r=a[r]; return r; } void ma(int x,int y,int q) { int fx,fy; fx = find(x); fy = find(y); if(fx != fy) { a[fx] = fy; sum=sum+q; } } int main() { int n,m; while(scanf("%d",&n)) { if(n==0) break; scanf("%d",&m); int i; for(i=1;i<=n;i++) a[i]=i; int j,min,temp,count; for(i=1;i<=m;i++) scanf("%d %d %d",&x[i],&y[i],&q[i]); for(i=1;i<=m;i++) { min=i; for(j=i;j<=m;j++) if(q[min]>q[j]) min=j; temp=q[min]; q[min]=q[i]; q[i]=temp; temp=x[min]; x[min]=x[i]; x[i]=temp; temp=y[min]; y[min]=y[i]; y[i]=temp; } sum=0; for(i=1;i<=m;i++) { ma(x[i],y[i],q[i]); count=0; for(j=1;j<=n;j++) if(a[j] == j) count++; if(count==0) break; } if(count==0) printf("%d\n",sum); else printf("?\n"); } } 我的代码 题目 描述 省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可)。经过调查评估,得到的统计表中列出了有可能建设公路的若干条道路的成本。现请你编写程序,计算出全省畅通需要的最低成本。 输入 测试输入包含若干测试用例。每个测试用例的第1行给出评估的道路条数 N、村庄数目M ( < 100 );随后的 N 行对应村庄间道路的成本,每行给出一对正整数,分别是两个村庄的编号,以及此两村庄间道路的成本(也是正整数)。为简单起见,村庄从1到M编号。当N为0时,全部输入结束,相应的结果不要输出。 输出 对每个测试用例,在1行里输出全省畅通需要的最低成本。若统计数据不足以保证畅通,则输出“?”。 样例输入 3 3 1 2 1 1 3 2 2 3 4 1 3 2 3 2 0 100 样例输出 3 ? 不知道错哪里.....我感觉我的思路没有错啊
首页 1 2 3 下一页