例5.3 还是畅通工程
#include<stdio.h> #include<algorithm> using namespace std; #define N 101 int tree[N]; struct edge { int a,b; int cost; bool operator < (const edge &A) const { return cost<A.cost; } }edge[6000]; int findroot(int x) { if(tree[x]==-1) return x; else { int tmp=findroot(tree[x]); tree[x]=tmp; return tmp; } } int main() { int n; while(scanf("%d",&n)!=EOF&&n!=0) { for(int i=1;i<=n;i++) tree[i]=-1; for(int i=0;i<n*(n-1)/2;i++) scanf("%d%d%d",&edge[i].a,&edge[i].b,&edge[i].cost); sort(edge,edge+n*(n-1)/2); int ans=0; for(int i=0;i<n*(n-1)/2;i++) { int ra=findroot(edge[i].a); int rb=findroot(edge[i].b); if(ra!=rb) { tree[ra]=rb; ans=ans+edge[i].cost; } } printf("%d\n",ans); } return 0; }例5.4 Freckles
#include<stdio.h> #include<math.h> #include<algorithm> using namespace std; #define N 101 int tree[N]; int findroot(int x) { if(tree[x]==-1) return x; else { int tmp=findroot(tree[x]); tree[x]=tmp; return tmp; } } struct edge { int a,b; double cost; bool operator < (const edge &A) const { return cost<A.cost; } }edge[6000]; struct point { double x,y; double getDistance(point A) { double tmp=(x-A.x)*(x-A.x)+(y-A.y)*(y-A.y); return sqrt(tmp); } }list[1000]; int main() { int n; while(scanf("%d",&n)!=EOF) { for(int i=1;i<=n;i++) scanf("%lf%lf",&list[i].x,&list[i].y); int size=0; for(int i=1;i<=n;i++) { for(int j=i+1;j<=n;j++) { edge[size].a=i; edge[size].b=j; edge[size].cost=list[i].getDistance(list[j]); size++; } } sort(edge,edge+size); double ans=0; for(int i=1;i<=n;i++) tree[i]=-1; for(int i=0;i<size;i++) { int ra=findroot(edge[i].a); int rb=findroot(edge[i].b); if(ra!=rb) { tree[ra]=rb; ans=ans+edge[i].cost; } } printf("%.2lf\n",ans); } return 0; }练1：Jungle Roads
#include<stdio.h> #include<algorithm> using namespace std; #define N 28 int tree[N]; int findroot(int x) { if(tree[x]==-1) return x; else { int tmp=findroot(tree[x]); tree[x]=tmp; return tmp; } } struct edge { int a,b; double cost; bool operator < (const edge &A) const { return cost<A.cost; } }edge[6000]; int main() { int n; while(scanf("%d",&n)!=EOF&&n!=0) { int size=0; for(int i=1;i<n;i++) { char node; int num; getchar(); //必须有!!!! scanf("%c%d",&node,&num); for(int j=0;j<num;j++) { char tc; int tn; getchar(); //必须有!!!! scanf("%c%d",&tc,&tn); edge[size].a=(int)(node-'A'+1); edge[size].b=(int)(tc-'A'+1); edge[size].cost=tn; size++; } } sort(edge,edge+size); for(int i=1;i<=n;i++) tree[i]=-1; int ans=0; for(int i=0;i<size;i++) { int ra=findroot(edge[i].a); int rb=findroot(edge[i].b); if(ra!=rb) { tree[ra]=rb; ans=ans+edge[i].cost; } } printf("%d\n",ans); } return 0; }注意scanf()与getchar() 可见博客scanf与getchar的区别
练2：畅通工程
#include<stdio.h> #include<algorithm> using namespace std; #define N 101 int tree[N]; struct edge { int a,b; int cost; bool operator < (const edge &A) const { return cost<A.cost; } }edge[6000]; int findroot(int x) { if(tree[x]==-1) return x; else { int tmp=findroot(tree[x]); tree[x]=tmp; return tmp; } } int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF&&n!=0) { for(int i=1;i<=m;i++) tree[i]=-1; for(int i=0;i<n;i++) scanf("%d%d%d",&edge[i].a,&edge[i].b,&edge[i].cost); sort(edge,edge+n); int ans=0; for(int i=0;i<n;i++) { int ra=findroot(edge[i].a); int rb=findroot(edge[i].b); if(ra!=rb) { tree[ra]=rb; ans=ans+edge[i].cost; } } int tmp=0; for(int i=1;i<=m;i++) { if(findroot(i)==i) tmp++; } if(tmp==1) printf("%d\n",ans); else printf("?\n"); } return 0; }练3：继续畅通工程
#include<stdio.h> #include<algorithm> using namespace std; #define N 101 int tree[N]; struct edge { int a,b; int cost; bool operator < (const edge &A) const { return cost<A.cost; } }edge[6000]; int findroot(int x) { if(tree[x]==-1) return x; else { int tmp=findroot(tree[x]); tree[x]=tmp; return tmp; } } int main() { int n,tmp; while(scanf("%d",&n)!=EOF&&n!=0) { for(int i=1;i<=n;i++) tree[i]=-1; for(int i=0;i<n*(n-1)/2;i++) { scanf("%d%d%d%d",&edge[i].a,&edge[i].b,&edge[i].cost,&tmp); if(tmp==1) edge[i].cost=0; } sort(edge,edge+n*(n-1)/2); int ans=0; for(int i=0;i<n*(n-1)/2;i++) { int ra=findroot(edge[i].a); int rb=findroot(edge[i].b); if(ra!=rb) { tree[ra]=rb; ans=ans+edge[i].cost; } } printf("%d\n",ans); } return 0; }