省政府“”畅通工程”目标是是全省任何两个村庄之间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公、公路可达即可）。现得到城镇道路统计表，表中列出了任意两城镇建见修建道路的经费，以及该道路是否已经修通的状态，现请编写程序，计算出全省畅通需要的最低成本 输入 测试输入包含若干测试用例，每个测试用例的第一行给出村庄数目N（1<N<100） 随后的n(n-1)/2行对应村庄的编号道路的成本及修建状态，每行给出4正整数，分别表示两个村庄的编号（从一到n），此两个村庄的道路成本，已经修建的状态，1 表示已经 0表示未建 当n为0时出入结束 输出 每个测试用例的输出占一行，输出全省畅通需要的最低成本 样例输入 3 1 2 1 0 1 3 2 0 2 3 4 0 3 1 2 1 0 1 3 2 0 2 3 4 1 3 1 2 1 0 1 3 2 1 2 3 4 1 0 样例输出 3 1 0
#include <iostream> #include <cstring> #include <algorithm> #include <cstdio> using namespace std; const int N=105; int map[N][N],f[N]; int n,a,b,c,d,cnt,sum; struct node{ int st,ed,cost; }route[N*N]; bool cmp(node a,node b){ return a.cost<b.cost; } int find(int x){ while(x!=f[x]){ x=f[x]; } return f[x]; } int connect(int x,int y){ int xx=find(x); int yy=find(y); if(xx!=yy){ f[xx]=yy; return true; } return false; } int main(){ while(scanf("%d",&n)&&n){ cnt=0; sum=0; memset(map,0,sizeof(map)); for(int i=1;i<=n;i++){ f[i]=i; } for(int i=0;i<n*(n-1)/2;i++){ scanf("%d %d %d %d",&a,&b,&c,&d);//cin>>a>>b>>c>>d; if(d){ connect(a,b); } else{ route[cnt++]=node{a,b,c}; } } sort(route,route+cnt,cmp); for(int i=0;i<cnt;i++){ sum+=connect(route[i].st,route[i].ed)==true?route[i].cost:0; } printf("%d\n",sum); } return 0; }