题目描述
某地区经过对城镇交通状况的调查,得到现有城镇间快速道路的统计数据,并提出“畅通工程”的目标:使整个地区任何两个城镇间都可以实现快速交通(但不一定有直接的快速道路相连,只要互相间接通过快速路可达即可)。现得到城镇道路统计表,表中列出了任意两城镇间修建快速路的费用,以及该道路是否已经修通的状态。现请你编写程序,计算出全地区畅通需要的最低成本。
输入格式:
输入格式
输入的第一行给出村庄数目NNN (1≤N≤100);随后的N(N−1)/2行对应村庄间道路的成本及修建状态:每行给出4个正整数,分别是两个村庄的编号(从1编号到N),此两村庄间道路的成本,以及修建状态 — 1表示已建,0表示未建。
输出格式
输出全省畅通需要的最低成本。
输入样例
4
1 2 1 1
1 3 4 0
1 4 1 1
2 3 3 0
2 4 2 1
3 4 5 0
输出样例
3
分析
本题最初的一些点是互相连接的,所以需要先用并查集把这些点连接起来,之后把没有连接的点加入到边集edges[]中,然后使用克鲁斯卡尔算法求最小生成树,每循环一次判断所有点是否在同一个集合中(check()函数),如果是直接返回答案。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n,fa[N],idx;
struct edg{
int a,b,w;
bool operator < (const edg &p) const
{
return w < p.w;
}
}edges[10010];
int find(int x)
{
if(fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
}
bool check()
{
set<int> s;
for(int i=1;i<=n;i++)
{
s.insert(fa[i]);
if(s.size()>1) return false;
}
return true;
}
int ans,cnt;
void kruskal()
{
sort(edges,edges+idx);
for(int i=0;i<idx;i++)
{
int a=edges[i].a,b=edges[i].b,w=edges[i].w;
int faa=find(a),fbb=find(b);
if(faa!=fbb)
{
fa[faa]=fbb;
ans+=w;
}
if(check()) break; //检查所有点是否都在一个集合中
}
}
int main()
{
for(int i=0;i<N;i++) fa[i]=i;
cin>>n;
int m=n*(n-1)/2;
int a,b,w,flag;
for(int i=0;i<m;i++)
{
cin>>a>>b>>w>>flag;
if(flag==0) //两点不连接,直接加入边集
{
edges[idx]={a,b,w};
idx++;
}
else{ //两点互相连接,并查集建立连接
int faa=find(a),fbb=find(b);
if(faa!=fbb)
{
fa[faa]=fbb;
}
}
}
kruskal(); //求最小生成树
cout<<ans;
return 0;
}