继续畅通工程

省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。现得到城镇道路统计表，表中列出了任意两城镇间修建道路的费用，以及该道路是否已经修通的状态。现请你编写程序，计算出全省畅通需要的最低成本。 Input 测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( 1< N < 100 )；随后的 N(N-1)/2 行对应村庄间道路的成本及修建状态，每行给4个正整数，分别是两个村庄的编号（从1编号到N），此两村庄间道路的成本，以及修建状态：1表示已建，0表示未建。 当N为0时输入结束。 Output 每个测试用例的输出占一行，输出全省畅通需要的最低成本。 Sample Input 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 Sample Output 3 1

0

题意：

题解：先判断每条路的状态，如果是修好的，就让它们的成本是0；如果没修，就让成本给出的成本

摘要：最小生成树是为了解决一些最优解的一种手段，比如给你N个城市以及城市之间的距离，要你求出能连接所有城市的最短距离。

#include<iostream> #include<algorithm> using namespace std; int set[105]; struct node{ int x; int y; int cost; }road[10005]; //成本排序 int cmp(node a,node b){ //判断为true return a.cost<b.cost; } int find(int x){ int r=x; while(set[r]!=r) r=set[r]; return r; } int merge(int a,int b){ a=find(a); b=find(b); if(a!=b){ set[b]=a; return 1; } else return 0; } void Init_set(){ for(int i=0;i<105;i++) set[i]=i; } int main(){ int n; int m; int flag; while(cin>>n,n){ Init_set(); m=n*(n-1)/2; for(int i=0;i<m;i++){ //此题用不了cin 不知为甚 scanf("%d%d%d%d",&road[i].x,&road[i].y,&road[i].cost,&flag); //就多了这一步，注意修好的路不需要再花钱 if(flag==1) road[i].cost=0; } sort(road,road+m,cmp); int sum=0; for(int i=0;i<m;i++) if(merge(road[i].x,road[i].y)) sum+=road[i].cost; cout<<sum<<endl; } return 0; }