蓝桥杯历届试题城市建设满分代码(最小生成树kruscal算法）

Dabria ·

更新时间:2024-11-13

· 560 次阅读

问题描述
　　栋栋居住在一个繁华的C市中，然而，这个城市的道路大都年久失修。市长准备重新修一些路以方便市民，于是找到了栋栋，希望栋栋能帮助他。
　　C市中有n个比较重要的地点，市长希望这些地点重点被考虑。现在可以修一些道路来连接其中的一些地点，每条道路可以连接其中的两个地点。另外由于C市有一条河从中穿过，也可以在其中的一些地点建设码头，所有建了码头的地点可以通过河道连接。
　　栋栋拿到了允许建设的道路的信息，包括每条可以建设的道路的花费，以及哪些地点可以建设码头和建设码头的花费。
　　市长希望栋栋给出一个方案，使得任意两个地点能只通过新修的路或者河道互达，同时花费尽量小。
输入格式
　　输入的第一行包含两个整数n, m，分别表示C市中重要地点的个数和可以建设的道路条数。所有地点从1到n依次编号。
　　接下来m行，每行三个整数a, b, c，表示可以建设一条从地点a到地点b的道路，花费为c。若c为正，表示建设是花钱的，如果c为负，则表示建设了道路后还可以赚钱（比如建设收费道路）。
　　接下来一行，包含n个整数w_1, w_2, …, w_n。如果w_i为正数，则表示在地点i建设码头的花费，如果w_i为-1，则表示地点i无法建设码头。
　　输入保证至少存在一个方法使得任意两个地点能只通过新修的路或者河道互达。
输出格式
　　输出一行，包含一个整数，表示使得所有地点通过新修道路或者码头连接的最小花费。如果满足条件的情况下还能赚钱，那么你应该输出一个负数。
样例输入
5 5
1 2 4
1 3 -1
2 3 3
2 4 5
4 5 10
-1 10 10 1 1
样例输出
9

具体思路可以参考博客：蓝桥杯城市建设（kruscal变形）
这里给大家列举几个小坑：两遍kruscal记得都先进行初始化，node结构体数组要开大一点。
做完也有两个比较简单的kruscal和并查集的题可以去巩固一下：HOJ1232并查集，HOJ1863畅通工程Kruscal，隔壁两篇博客也有这两个的ac代码。

#include 
#include 
#include 
#include 
using namespace std;
struct Node{
	int a;
	int b;
	int cost;
};
Node node[200005];
int par[10010];
void init(int n){
	for(int i = 0;i <= n;i++){
		par[i] = i;
	}
}
int cmp(const Node& a,const Node& b){
	return a.cost < b.cost;
}
int find(int x){
	if(x == par[x]) return x;
	return par[x] = find(par[x]);
}
int kruscal(int n,int m){
	init(n);
	sort(node,node+m,cmp);
	int num = 0,sum = 0;
	for(int i = 0;i < m;i++){
		int fx = find(node[i].a);
		int fy = find(node[i].b);
		int cst = node[i].cost;
		if(fx != fy || cst < 0){
			sum += cst;
			if(fx != fy){
				par[fx] = fy;
				num++;
			}
		}
	}
	if(num < n - 1) sum = -1;
	return sum;
}
int main(){
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i = 0;i < m;i++){
		scanf("%d %d %d",&node[i].a,&node[i].b,&node[i].cost);
	}
	int allcost1 = kruscal(n,m);
	for(int i = 1;i <= n;i++){		
		scanf("%d",&node[m].cost);
		if(node[m].cost != -1){
			node[m].a = 0;
			node[m].b = i;
			m++;
		}
	} 
	int allcost2 = kruscal(n+1,m);
	if(allcost1 == -1){
		cout<<allcost2<<endl;
	}
	else{
		int res = min(allcost1,allcost2);
		cout<<res<<endl;
	}
	return 0;
}