考研机试真题--继续畅通工程--浙江大学
发布时间
阅读量：
阅读量
关键字：最小生成树、Kruskal算法、并查集实现
题目：
题目描述
省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。现得到城镇道路统计表，表中列出了任意两城镇间修建道路的费用，以及该道路是否已经修通的状态。现请你编写程序，计算出全省畅通需要的最低成本。
输入描述:
测试输入包含若干测试用例。每个测试用例的第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
该算法的基本思路是基于Kruskal方法。在计算最小生成树的成本时，默认不考虑已经存在的道路。为了便于后续处理，在对所有边按照成本从小到大排序后，默认将已经存在的道路放置在靠前的位置。当选择加入最小生成树的第i条边的数量至少与cnt1相等时，则开始进行成本计算。
代码：
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
const int maxn = 10010;
int father[maxn];
struct Edge{
int a, b;
int weight;
bool state;
}edge[maxn];
bool cmp(Edge a, Edge b){
if(a.state != b.state) return a.state > b.state;
return a.weight < b.weight;
}
int findFather(int x){
if(father[x] == x) return x;
return findFather(father[x]);
}
int main(){
int n;
// freopen("a.txt", "r", stdin);
while(cin >> n && n != 0){
int fa, fb;
int cnt1 = 0, cnt2 = 0; //cnt1:已通的道路数 cnt2:已建好的最小生成树的边数
int m = n * (n - 1) / 2;
for(int i = 1; i <= n; ++i){
father[i] = i;
}
for(int i = 0; i < m; ++i){
cin >> edge[i].a >> edge[i].b >> edge[i].weight >> edge[i].state;
if(edge[i].state == 1) cnt1 ++;
}
sort(edge, edge + m, cmp);
int ans = 0;
for(int i = 0; i < m; ++i){
fa = findFather(edge[i].a);
fb = findFather(edge[i].b);
if(fa != fb){
father[fa] = fb;
cnt2++;
if(i >= cnt1) ans += edge[i].weight;
}
if(cnt2 == n - 1) break;
}
cout << ans << endl;
}
return 0;
}全部评论 (0)
还没有任何评论哟~