题目描述：

省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。现得到城镇道路统计表，表中列出了任意两城镇间修建道路的费用，以及该道路是否已经修通的状态。现请你编写程序，计算出全省畅通需要的最低成本。

输入：

测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( 1< N < 100 )；随后的 N(N-1)/2 行对应村庄间道路的成本及修建状态，每行给4个正整数，分别是两个村庄的编号（从1编号到N），此两村庄间道路的成本，以及修建状态：1表示已建，0表示未建。

当N为0时输入结束。

输出：

每个测试用例的输出占一行，输出全省畅通需要的最低成本。

样例输入：

样例输出：

3
1
0

代码：

#include <iostream>  
#include <vector>  
#include <algorithm>  
#define MAXSIZE 1000   
using namespace std;  
struct Edge{  
int start,end;  
int weight;  
Edge(){  
}  
Edge(int start,int end,int weight){  
    this->start=start;  
    this->end=end;  
    this->weight=weight;  
}  
bool operator<(const Edge &e)const{  
    return weight<e.weight;  
}  
};   

struct Set{ //UnionFindSet 从0开始   
int root[MAXSIZE];  
int setSize;  
vector<Edge> edge;  
int initSet(int setSize){  
    this->setSize=setSize;  
    edge.clear();  
    for (int i=0;i<setSize;i++){  
        root[i]=-1;  
    }  
}  
int findRoot(int x){//reduce deep  
    if (root[x]==-1)  
        return x;  
    else   
        return root[x]=findRoot(root[x]);  
}  
int unionSet(int x,int y){  
    int xroot=findRoot(x);  
    int yroot=findRoot(y);  
    if(xroot!=yroot){//if x&y are not in the same set 那么说明其中一个还是初态，一次都没有并过  
        root[xroot]=yroot; //merge xset into yset   
        return yroot;  
    }   
    return -1;  
}  
void print(){  

    cout<<endl;  
}  
};  
int main(){  
int n;  
int x,y;  
int weight,totalWeight;  
Set set;      
bool built;  
while (cin>>n,n){  
    //initiate  
    set.initSet(n);  
    totalWeight=0;  
    //input&create the edge list  
    for (int i=0;i<n*(n-1)/2;i++){  
        cin>>x>>y>>weight>>built;  
        x--;y--;  
        if(built==true)  
            set.unionSet(x,y);  
        else  
            set.edge.push_back(Edge(x,y,weight));  
    }  
    //sort  
    sort(&set.edge[0],&set.edge[0]+set.edge.size());  
    //union&cal totalWeight  
    for (int i=0;i<set.edge.size();i++){  
        if (set.unionSet(set.edge[i].start,set.edge[i].end)!=-1){//if merge the two sets  
            totalWeight+=set.edge[i].weight;  
        }  
    }  
    //output  
        cout<<totalWeight<<endl;  
}   
return true;  
}

作者提醒

依然是最小生成树。此题的不同是有的路径已经建好了，体现在具体实现上就是在进行kruskal之前现将这两个点进行并集，这样在kruskal时就作为一个个的集合出现。

收获如下：

　　①已建路径的预处理（如上）

　　②对cin：

　　1.只能抓取int类型进int变量，不能将char类型自动转化为int类型塞进int变量：

char c;  
int i;  
cin>>i;  
输入“A”→出错

2.能抓取“1”、“0”进bool变量：

bool b;  
cin>>b;  
输入“1”或“0”→正确  
注意：只能是1或0，输入其他数字出错