zjh

用户名：speaksoftly

访问量：24718

签　名：

搞spring去了...不能愉快的刷题了...

等　　级
排　　名	172
经　　验	6955
参赛次数	10
文章发表	37
年　　龄	0
在职情况	学生
学　　校	海南
专　　业

　　自我简介：

TA的其他文章

信息学奥赛一本通T1242-网线主管（C++代码）二分
浏览：1468

你可能喜欢

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C++代码）（手动优化一下计算）

蓝桥杯历届试题-城市建设（C++代码）并查集&最小生成树kruskal

　　作者: zjh　　　　发表时间：2019-07-15 02:19:15 浏览：1226　|　评论：2　

原题链接：蓝桥杯历届试题-城市建设

```cpp

注意：根据kruskal的思想，如果已经有一条最小的边了，那么其他的边就不再构建了，但是这里要做一下改变，因为有的边权是负数，那这条边我们必须要构建（有钱赚）
重点：学会并查集，最小生成树
难点：分析不同的情况挨个处理
情况1：只建立公路，且生成树必须形成（存在任意点之间有边可达），所花费的最小代价
情况2：只建立公路 和 建立公路、码头，两者取一个min，前提，只建立公路必须可以形成树
情况3：公路建立不出来（不能生产树）那么就建立公路、码头所花费的最小代价就是答案

ps:为什么用最小生成树&并查集? 因为求最小花费使得各个城市可互达，首先想到的就是最小生成树，而kruskal又依赖并查集，所以自然用生成树和并查集

#include "iostream"
#include "cstdio"
#include "cstdlib"
#include "cstring"
#include "cmath"
#include "algorithm"
#include "queue"
#include "vector"
#include "stack"
#include "map"

using namespace std;

typedef long long ll;
const int maxn = 10010;			//点的数量
const int maxm = 110010;		   //边的数量
const int INF = 0x7fffffff;

typedef struct {
	int x, y;	//存边
	int price;	//存边权
}Edge;

// A : 每个点建立码头的费用, fa : 并查集核心数组
int n, m, A[maxn], fa[maxn];
Edge E[maxm];	//存边，权

/** 按照花费的代价从小到大排序 */
bool cmp(Edge a, Edge b) {
	return a.price < b.price;
}

/** 并查集初始化, 会用到0, 所以从0开始 */
void init() {
	for(int i = 0; i <= n; ++i) {
		fa[i] = i;
	}
}

/** 找祖宗 */
int find(int x) {
	return x == fa[x] ? x : fa[x] = find(fa[x]);
}

/**
 * 最小生成树kruskal算法核心
 * node : 节点的数量, 用于判断是否能建成树或图, 也用于情况 1 与情况 2 、 3 的区分
 * length : 边的数量, 用于排序和处理有码头、无码头边的区分
 */
int kruskal(int node, int length) {
	init();	//初始化fa
	sort(E, E + length, cmp);	//排序
	int res = 0;	//最小花费的结果
	for(int i = 0; i < length; ++i) {
		int p1 = find(E[i].x);
		int p2 = find(E[i].y);
		if(p1 != p2) {
			fa[p2] = p1;
			res += E[i].price;
			node--;	//根据kruskal思想，最小生成树边的数量应为n - 1，但是这里因为有权值为负的情况，所以只考虑树能不能建成（即node <= 1)
		}else {
			//如果该边已经有了最小的，并且当前边的权值是负数，那么...我要钱 (逃
			if(E[i].price < 0) {
				res += E[i].price;
			}
		}
	}
	//树建不成 Orz (当加入码头边时，必能建成，只要点与点之间有码头就能互通)
	if(node > 1) {
		return INF;
	}
	return res;
}

int main() {
	cin >> n >> m;
	for(int i = 0; i < m; ++i) {
		cin >> E[i].x >> E[i].y >> E[i].price;
	}
	int cnt = m;	//用于保存加上每个点加上码头之后边的总数量
	for(int i = 1; i <= n; ++i) {
		cin >> A[i];
		if(A[i] != -1) {
		//表示从 0 和 i 节点有边可互通，先假设 0 节点有码头, 实际上是不知道与谁互通，但很明确的是只要两点有码头就可互通，并且费用都是自身建立码头的价格
			E[cnt].x = 0;
			E[cnt].y = i;
			E[cnt].price = A[i];
			cnt++;
		}
	}
	//注意此时不能把 0 结点和码头的边算进去， 求的是只建公路，所以边的数量只有 m， 点的数量只有 1 ~ n
	int res = kruskal(n, m);					//情况1
	//以下需要将 0 结点和码头的边算进去计算， 点的数量 0 ~ n，边的数量cnt
	if(res != INF) {
		res = min(res, kruskal(n + 1, cnt));	//情况2
	}else {
		res = kruskal(n + 1, cnt);		 	 //情况3
	}
	cout << res << endl;
	return 0;
}
```

0.0分

18 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

超

为啥要分情况？

2021-10-19 20:53:16

wdt

测试评论

2020-10-11 08:33:27

zjh

TA的其他文章

你可能喜欢

C二级辅导-进制转换（C++代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

母牛的故事（C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C++代码）（手动优化一下计算）

蓝桥杯历届试题-城市建设（C++代码）并查集&最小生成树kruskal

评论区

精彩推荐

C二级辅导-统计字符（C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

大神老白（C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

1011题解

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

A+B for Input-Output Practice (V) （C语言代码）

输出九九乘法表（C语言代码）

zjh

TA的其他文章

你可能喜欢

C二级辅导-进制转换 （C++代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

母牛的故事 （C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C++代码）（手动优化一下计算）

蓝桥杯历届试题-城市建设 （C++代码）并查集&最小生成树kruskal

评论区

精彩推荐

C二级辅导-统计字符 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

大神老白 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

1011题解

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

A+B for Input-Output Practice (V) （C语言代码）

输出九九乘法表 （C语言代码）

C二级辅导-进制转换（C++代码）

母牛的故事（C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C++代码）（手动优化一下计算）

蓝桥杯历届试题-城市建设（C++代码）并查集&最小生成树kruskal

　　评论区

C二级辅导-统计字符（C语言代码）

大神老白（C语言代码）

输出九九乘法表（C语言代码）