#C++1745—— 继续畅通工程（带权并查集）

解题思路:

找出有根节点的“家族”即还未畅通的“村庄群”，按权值排序后归并统计数量。

注意事项:

对于之前已经连接的道路，先预处理合并，再用cmp处理权值较小的边。

AC代码:

#include <iostream>
#include <algorithm>
using namespace std;
int father[115],ans;
struct roads 
{
    int a,b;//村庄标号 
    int cost,flag;//费用、修建标记 
}road[5005];
void Init(int n)//初始化
{
    for(int i=1;i<=n;i++)
        father[i]=i;
}
int Find(int x)//路径压缩 
{
      return x==father[x]?x:father[x]=Find(father[x]);//相当于if(x==father[x])return x;else return father[x]=Find(father[x]);
}
void Union(int i)//合并 
{
    int a=Find(road[i].a),b=Find(road[i].b);
    if(a!=b)father[a]=b,ans+=road[i].cost;
}
bool cmp(const roads &a,const roads &b)//定义排序规则,此参数可以加快速度 
{
      return a.cost<b.cost;
}
int main()
{
    int n,m;
    while(cin>>n&&n)//多组输入,以0结束 
    {
         Init(n);
         m=n*(n-1)/2;//随后的 N(N-1)/2行 
         for(int i=0;i<m;i++)
         {
            cin>>road[i].a>>road[i].b>>road[i].cost>>road[i].flag;
            if(road[i].flag)Union(i); //输入顺便把已存在的路连通起来（预处理） 
         }
         sort(road,road+m,cmp);//按条件排序,保证成本最少
         for(int i=ans=0;i<m;i++)
            Union(i);//最后遍历把能并的并起来，因为已存在的已经并起来了，已经在一个家族里，所以不会再并了（不影响最终结果）
         cout<<ans<<endl;
     }
    return 0;
 }//dongdong