继续畅通工程
原题链接：https://acm.hdu.edu.cn/showproblem.php?pid=1879
Problem Description
省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。现得到城镇道路统计表，表中列出了任意两城镇间修建道路的费用，以及该道路是否已经修通的状态。现请你编写程序，计算出全省畅通需要的最低成本。
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
与hdoj 1863 比起来，多了一个状态信息
1 #include <string.h> 2 #include <stdio.h> 3 #include <algorithm> 4 #include <math.h> 5 #include <iostream> 6 #include <queue> 7 using namespace std; 8 const int maxn=100+1; 9 int father[maxn]; 10 11 void init(int n){ 12 for(int i=1;i<=n;i++) father[i]=i; 13 } 14 15 int find(int x){ 16 int a=x; 17 while(x!=father[x]){ 18 x=father[x]; 19 } 20 while(a!=father[a]){ //路径压缩 21 int z=a; 22 a=father[a]; 23 father[z]=x; 24 } 25 return x; 26 } 27 28 29 30 bool Union(int u, int v){ 31 int a=find(u); 32 int b=find(v); 33 if(a!=b){ 34 father[a]=b; 35 return true; 36 }else return false; 37 } 38 39 struct edge{ 40 int src, dest, cost,stat; 41 bool operator < (const edge&n) const{ 42 return cost > n.cost; 43 } 44 }; 45 46 47 int main(){ 48 int n,m; 49 edge e; 50 while(scanf("%d",&n)!=EOF && n){ 51 priority_queue<edge> q; 52 init(n) ; 53 m=n*(n-1)/2; 54 int ans=0,count=0; 55 while(m--){ 56 scanf("%d%d%d%d",&e.src, &e.dest, &e.cost, &e.stat); 57 if (e.stat==1){ 58 if(Union(e.src, e.dest)) count++; 59 }else q.push(e); 60 } 61 62 while(!q.empty() && (count!=n-1)){ 63 e=q.top(); 64 q.pop(); 65 if(Union(e.src, e.dest)){ 66 count++; 67 ans+=e.cost; 68 } 69 } 70 printf("%d ",ans); 71 } 72 return 0; 73 74 }