题目描述
省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。现得到城镇道路统计表，表中列出了任意两城镇间修建道路的费用，以及该道路是否已经修通的状态。现请你编写程序，计算出全省畅通需要的最低成本。
输入描述:
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( 1< N < 100 )；随后的 N(N-1)/2 行对应村庄间道路的成本及修建状态，每行给4个正整数，分别是两个村庄的编号（从1编号到N），此两村庄间道路的成本，以及修建状态：1表示已建，0表示未建。当N为0时输入结束。
输出描述:
每个测试用例的输出占一行，输出全省畅通需要的最低成本。
示例1
输入
复制
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
我刚开始的想法是，既然有已经修好的路，就先把这些修好的路全都加到集合中，即直接把他们Union，不加其长度，然后再将剩下的排序，按Kruskal的算法来进行。但是这种想法可能有什么问题，只过了一般的样例
AC的代码是：一旦路径已建好，将其长度值赋值为0，然后所有路径一致看待
#include<iostream>
#include<algorithm>
using namespace std;const int MAXN=101;
int father[MAXN];
int height[MAXN];struct edge {int from;int to;int len;int build;bool operator < (edge a)const {
// if(build && !a.build){ //已建好的顺序在前
// return true;
// }
// else if( build && a.build){
// return false;
// }
//
// else{ //若均未为建好或均已建好，长度小的在前return len<a.len;
// }}
} edges[MAXN*MAXN];void Init(int n) {for(int i=0; i<=n; i++) {father[i]=i;height[i]=0;}
}int Find(int i) {if(i!=father[i]) {father[i]=Find(father[i]);}return father[i];
}void Union(int i,int j) {i=Find(i);j=Find(j);if(i!=j) {if(height[i]>height[j]) {father[j]=i;} else if(height[j]>height[i]) {father[i]=j;} else {father[j]=i;height[i++];}}return ;
}int Krual(int n,int edgenumber) {Init(n);int sum=0;sort(edges,edges+edgenumber);for(int i=0; i<edgenumber; i++) {
// if(edges[i].build){
// Union(edges[i].from,edges[i].to);
// }
// else{
// if(Find(edges[i].from)!=Find(edges[i].to)){
// Union(edges[i].from,edges[i].to);
// sum+=edges[i].len;
// }
// }if(Find(edges[i].from)!=Find(edges[i].to)) {Union(edges[i].from,edges[i].to);sum+=edges[i].len;}}return sum;
}
int main() {int n;while(scanf("%d",&n)!=EOF) {if(n==0) {break;}int m=n*(n-1)/2;for(int i=0; i<m; i++) {scanf("%d%d%d%d",&edges[i].from,&edges[i].to,&edges[i].len,&edges[i].build);if(edges[i].build==1){edges[i].len=0;} }printf("%d\n",Krual(n,m));}return 0;
}