本文主要是介绍poj2075Tangled in Cables，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
基础的最小生成树题，用的kruskal算法，稍后的博客我会给出证明以及此算法与拟阵的关系。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX =10005;
char name[MAX][30];
int last[MAX];struct edge{double l;int a,b;bool operator<(edge other)const{return l<other.l;}
}edg[MAX+1];void make(int n){for(int i=1;i<=n;i++){last[i]=i;}
}int find(int x){int p=x,t;while(p!=last[p])p=last[p];while(x!=p){t=last[x],last[x]=p,x=t;}return p;
}void un(int a,int b){last[a]=b;
}int main(){double l,in,ans;int n,m,a,b,aa,bb;char name1[30],name2[30];while(scanf("%lf",&l)!=EOF){scanf("%d",&n);getchar();for(int i=1;i<=n;i++){scanf("%s",name[i]);}ans=0,make(n);scanf("%d",&m);getchar();for(int i=1;i<=m;i++){scanf("%s %s %lf",name1,name2,&in);for(int j=1;j<=n;j++){if(strcmp(name1,name[j])==0)a=j;if(strcmp(name2,name[j])==0)b=j;}edg[i].l=in,edg[i].a=a,edg[i].b=b;}sort(edg+1,edg+m+1);for(int i=1;i<=m;i++){aa=find(edg[i].a),bb=find(edg[i].b);if(aa!=bb){un(aa,bb);ans+=edg[i].l;}}if(ans>l)printf("Not enough cable\n");elseprintf("Need %.1lf miles of cable\n",ans);}return 0;
}
这篇关于poj2075Tangled in Cables的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
