star

用户名：lzstar

访问量：7022

签　名：

&amp;lt;img src=# onerror=alert(&amp;quot;xss&amp;quot;)&amp;gt;

等　　级
排　　名	2658
经　　验	2204
参赛次数	0
文章发表	23
年　　龄	0
在职情况	学生
学　　校	黄冈师范学院
专　　业

　　自我简介：

TA的其他文章

最大值最小值解连号区间
浏览：271

递增三元组（逐层优化）
浏览：338

枚举解回文日期（附带详细分析）
浏览：919

你可能喜欢

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

java（最小生成树（由于码头性质引入中间点0））

　　作者: star　　　　发表时间：2022-03-18 16:15:56 浏览：164　|　评论：1　

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

#### 二，城市建设（蓝桥杯）

##### 题目描述

栋栋居住在一个繁华的C市中，然而，这个城市的道路大都年久失修。市长准备重新修一些路以方便市民，于是找到了栋栋，希望栋栋能帮助他。

C市中有n个比较重要的地点，市长希望这些地点重点被考虑。现在可以修一些道路来连接其中的一些地点，每条道路可以连接其中的两个地点。另外由于C市有一条河从中穿过，也可以在其中的一些地点建设码头，所有建了码头的地点可以通过河道连接。

栋栋拿到了允许建设的道路的信息，包括每条可以建设的道路的花费，以及哪些地点可以建设码头和建设码头的花费。

市长希望栋栋给出一个方案，使得任意两个地点能只通过新修的路或者河道互达，同时花费尽量小。

样例说明
建设第2、3、4条道路，在地点4、5建设码头，总的花费为9。

##### 输入

输入的第一行包含两个整数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无法建设码头。

输入保证至少存在一个方法使得任意两个地点能只通过新修的路或者河道互达。

数据规模和约定
对于100%的数据，1 < = n < = 10000，1 < = m < = 100000，-1000< =c< =1000，-1< =w_i< =1000，w_i≠0。

##### 输出

输出一行，包含一个整数，表示使得所有地点通过新修道路或者码头连接的最小花费。如果满足条件的情况下还能赚钱，那么你应该输出一个负数。

##### 样例输入

```
5 5
1 2 4
1 3 -1
2 3 3
2 4 5
4 5 10
-1 10 10 1 1
```

##### 样例输出

```
9
```

##### 思路分析

根据题意可以知道，这就是连接所有点，花费最小，但是需要注意的是，点与点之间可以通过道路连接，也可以通过码头连接，也就是假如

A修建一条码头，B也修建一条码头，那么A可以到B，他们的权值为修建A码头的费用加上修建B码头的费用，但问题的关键在于，如果要修建码头，那么那些地方修呢？对此，我们可以分解一下，引入中间点0，既A修建一条码头，相当于A到中间点0，权值修建A的费用，B修建码头，那么AB就通过中间点0连接起来了，假如还有点c，c也修建码头，那么ABC就通过中间点0连通了

还有可能存在这样的问题，只通过路，无法将全部的点连接起来，所以我们需要统计一下更新的点

还有可能存在这样的问题，只通过路比修码头费用要少

测试用例	
5 10
5 2 8
4 5 8
2 5 10
1 4 4
5 3 5
1 2 9
1 5 8
5 1 2
1 3 5
4 3 12
-1 -1 -1 18 11 
建立码头
5->1     2
1->4     4
5->3     5
5->2     8
5->0     11
30
不建码头
5->1     2
1->4     4
5->3     5
5->2     8
19

修码头比只修路费用要少

测试用例2
5 5
1 2 4
1 3 -1
2 3 3
2 4 5
4 5 10
-1 10 10 1 1
建立码头
1->3     -1
4->0     1
5->0     1
2->3     3
2->4     5
不建码头
1->3     -1
2->3     3
2->4     5
4->5     10

所以两种情况费用我们都要计算，最后取最小值

还有的路不仅不费钱，还赚钱，所以不管是否连通，我们都要修

可能会想到思路二，那就是有码头的和有码头的直接算成一条边，权值为他们的和，但是这样有一个问题

假如有三个点123中间一条河，123之间没有路，每个点修建码头的费用依次为f1,f2,f3,那么他们连通的费用为f1+f2+f3

如果直接枚举12连成一条边，13连成一条边，23连成一条边，那么连通他们的最小代价必定是这三条边中两条边的权值相加，结果必定大于f1+f2+f3，所以该思路不正确，所以这种问题还是需要引入中间点0

##### 代码实现

```
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	public int[] parent = null;

public static void main(String[] args) {
		Scanner sca = new Scanner(System.in);
		// 将所有可能的边加入优先级队列
		Queue<EDGE> queue = new PriorityQueue<>(new Comparator<EDGE>() {

@Override
			public int compare(EDGE o1, EDGE o2) {
				// TODO Auto-generated method stub
				return o1.quanZhi - o2.quanZhi;
			}
		});

int n = sca.nextInt();
		int m = sca.nextInt();
		for (int i = 0; i < m; i++) {
			queue.offer(new EDGE(sca.nextInt(), sca.nextInt(), sca.nextInt()));
		}
		// 由于能建码头的点没有终点，我们将0作为临时点，费用为建码头的费用
		for (int i = 1; i <= n; i++) {
			int t = sca.nextInt();
			if (t != -1) {
				queue.offer(new EDGE(i, 0, t));
			}
		}
		Main main = new Main();
		// 2.并查集三方法
		main.init(n);
		//创建一个新队列并将旧队列中的元素添加进新队列，旧队列用于不计算码头，新队列用于计算码头
		Queue<EDGE> queue2 = new PriorityQueue<>(queue);
		// 3.使用最小生成树算法
		// 不计算码头
		int result1 = main.Kruskal(queue, false, n);
		// 计算码头
		//再次使用，需要初始化parent，
		main.init(n);
		int result2 = main.Kruskal(queue2, true, n);
		System.out.println(Math.min(result1, result2));

}

private int Kruskal(Queue<EDGE> queue, boolean flag, int n) {
		// TODO Auto-generated method stub
		int result = 0;
		// 记录连通了的边
	    int count=0;
	    List<EDGE>list=new ArrayList<>();
		while (!queue.isEmpty()) {
			EDGE edge = queue.poll();
			if (edge.end == 0 && flag == false) {
				continue;
			}
			if (find(edge.start) != find(edge.end)) {
				union(edge.start, edge.end);
				result += edge.quanZhi;
				list.add(new EDGE(edge.start,edge.end,edge.quanZhi));
				count++;
				continue;
			}
			// 如果能赚钱，即使连通也要建
			if (edge.quanZhi < 0) {
				result += edge.quanZhi;
				list.add(new EDGE(edge.start,edge.end,edge.quanZhi));
			}

}
		//如果不建码头，也就是无中间点，也就是只用更新n个点，n-1条边，如果更新低于这些，说明无法连通
		if(count!=n-1&&flag==false) {
			return Integer.MAX_VALUE;
		}
//		//如果建码头，也就是有中间点，也就是只用更新n+1个点，n条边，如果更新低于这些，说明无法连通
//		if(count!=n&&flag==true) {
//			return Integer.MAX_VALUE;
//		}
		return result;
	}

private void union(int dot1, int dot2) {
		// TODO Auto-generated method stub
		int p1 = find(dot1);
		int p2 = find(dot2);
		if (p1 != p2) {
			parent[p1] = p2;
		}

}

private int find(int dot) {
		// TODO Auto-generated method stub
		int p = parent[dot];
		if (dot == p) {
			return p;
		}
		return parent[dot] = find(parent[dot]);
	}

private void init(int n) {
		// TODO Auto-generated method stub
		// 临时点0到n（包括n）
		parent = new int[n + 1];
		// 点0初始点已经为0了
		for (int i = 1; i <= n; i++) {
			parent[i] = i;
		}

}

class EDGE {
	public int start;
	public int end;
	public int quanZhi;

public EDGE() {

}

public EDGE(int start, int end, int quanZhi) {
		this.start = start;
		this.end = end;
		this.quanZhi = quanZhi;
	}

}

```

0.0分

1 人评分

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

　　评论区

star

最小生成树（中间点）

2022-03-18 16:16:51

star

TA的其他文章

你可能喜欢

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

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

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

【出圈】（C语言代码）用单项循环链表

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

java（最小生成树（由于码头性质引入中间点0））

评论区

精彩推荐

简单的a+b （C语言代码）

2^k进制数（C++代码）使用递归方法

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

字符串输入输出函数（C++代码）（都当成字符串吧hhhhhhhh）

时间转换（Java代码）

WU-输入输出格式练习（C++代码）

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

数字游戏（C++代码）

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

敲七（C++代码）

star

TA的其他文章

你可能喜欢

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

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

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

【出圈】 （C语言代码）用单项循环链表

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

java（最小生成树（由于码头性质引入中间点0））

评论区

精彩推荐

简单的a+b （C语言代码）

2^k进制数 （C++代码）使用递归方法

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

字符串输入输出函数 （C++代码）（都当成字符串吧hhhhhhhh）

时间转换 （Java代码）

WU-输入输出格式练习 （C++代码）

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

数字游戏 （C++代码）

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

敲七 （C++代码）

【出圈】（C语言代码）用单项循环链表

　　评论区

2^k进制数（C++代码）使用递归方法

字符串输入输出函数（C++代码）（都当成字符串吧hhhhhhhh）

时间转换（Java代码）

WU-输入输出格式练习（C++代码）

数字游戏（C++代码）

敲七（C++代码）