题目描述
高铁城市圈对人们的出行、经济的拉动效果明显。每年都会规划新的高铁城市圈建设。 在给定：城市数量，可建设高铁的两城市间的修建成本列表、以及结合城市商业价值会固定建设的两城市建高铁。
请你设计算法，达到修建城市高铁的最低成本。 注意，需要满足城市圈内城市间两两互联可达 (通过其他城市中转可达也属于满足条件)
输入描述
- 第一行，包含此城市圈中城市的数量、可建设高铁的两城市间修建成本列表数量、必建高铁的城市列表。三个数字用空格间隔。
- 可建设高铁的两城市间的修建成本列表，为多行输入数据，格式为3个数字，用空格分隔，长度不超过1000。
- 固定要修建的高铁城市列表，是上面参数2的子集，可能为多行，每行输入为2个数字，以空格分隔。
城市 id 从 1 开始编号，建设成本的取值为正整数，取值范围均不会超过1000
输出描述
修建城市圈高铁的最低成本，正整数。如果城市圈内存在两城市之间无法互联，则返回 -1。
用例
用例1
--输入
3 3 0
1 2 10
1 3 100
2 3 50
--输出
60
--说明
3 3 0 城市圈数量为3，表示城市id分别为1,2,3
1 2 10 城市1，2间的高铁修建成本为10
1 3 100 城市1，3间的高铁修建成本为100
2 3 50 城市2，3间的高铁修建成本为50
满足修建成本最低，只需要建设城市1，2间，城市2，3间的高铁即可，城市1，3之间可通过城市2中转来互联。
这样最低修建成本就是60。用例2
--输入
3 3 1
1 2 10
1 3 100
2 3 50
1 3
--输出
110
--说明
无题目解析
这一道比较陌生了，涉及到了最小生成树，学习一下解法
生成树的概念
在无向 连通图 中，生成树是指包含了全部顶点的极小连通子图。
生成树
包含原图全部的 n 个顶点和 n-1 条边。 (注意，边的数量一定是 n-1 )
- 如上图就是一个 无向联通图，可以基于如上的 连通图，产生多个生成树
- 如下例子
- 如上图，使用
条边连接了
个顶点，这样就从无向连通图中产生了 生成树
为什么只能有 条边呢？
- 因为少一条边的话，生成树无法连接所有顶点，多一条边则会形成环。
- 生成树的两个最重要的特性
- 包含所有顶点
- 无环
学习最小生成树
在 无向联通图 中，每一条边都有权重值。如下图
如上图
- 节点 V1、V3 之间的权重值是 2
- 节点 V3、V4 之间的权重值是 6
最小生成树指的是，生成树中 条边的权重值之和最小
最小生成树计算过程
- 在 无向图 联通网中，可以把所有的顶点分为 A、B 两类
- 以 图A1 为例，一共有 6 个顶点
V1, V2, V3, V4, V5, V6 - 首先可以把所有的顶点分别存入两个集合A、B中
A={}, B={V1,V2,V3,V4,V5,V6} - 现在假设从点 V1 出发，现在将点 V1 加入到 集合 A 中。那么从 A 类集合到到达 B 类集合的顶点一共有 3 个
V1-V2 权重值=7V1-V3 权重值=2V1-V4 权重值=6
最小路线是 V1-V3——那么把点 V3 加入到 A 类集合中A={V1,V3}, B={V2, V4, V5, V6}- 此时从 V3 点出发，到达 B 类集合的路线一共有 6条路线
V1-V2V1-V4V3-V2V3-V4V3-V5V3-V6- 最小权重值是
V3-V6 = 5，所以 把 点 V6 加入到集合中
- 以此类推
算法的具体实现
package com.hw;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
/**
* desc : <a href="https://fcqian.blog.csdn.net/article/details/128249625">最优高铁城市修建方案</a>
* <p>
* create time : 2023/8/2 09:35
*/
public class RailwayPlanning {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 第一行固定三个数字
while (in.hasNextInt()) {
// 城市数量.
int cityNum = in.nextInt();
// 可建设高铁的两城市间 - 成本列表数量.
// ex：有 5 个城市，1 2 100 表示城市 1 2 直接修建高铁的成本是100
int costNum = in.nextInt();
// 必定要修建高铁的城市列表数量
int mustCityNum = in.nextInt();
// 成本列表数量.
int[][] costs = new int[costNum][3];
for (int i = 0; i < costNum; i++) {
for (int j = 0; j < 3; j++) {
costs[i][j] = in.nextInt();
}
}
// 必定要修建高铁的城市列表数量，每一行两个数字
int[][] mustCities = new int[mustCityNum][2];
for (int i = 0; i < mustCityNum; i++) {
mustCities[i][0] = in.nextInt();
mustCities[i][1] = in.nextInt();
}
railwayPlanning(cityNum, costs, mustCities);
}
}
/* 目的，求得修建高铁的最低成本，需要满足两两互联可达。（通过其它城市中转可达也属于满足条件）
*
* ｜-存在有固定需要修建的高铁列表.
*
*/
/**
* code to write.
*
* @param cityNum 城市列表.
* @param costs 在各个城市之间修建高铁的 成本列表
* @param mustCities 必须修建高铁的城市 列表
*/
private static void railwayPlanning(int cityNum, int[][] costs, int[][] mustCities) {
UnionFindSet union = new UnionFindSet(cityNum);
// 先计算固定需要修建的高铁列表.
// 为了方便统计，这里对数据进行转化处理一下 ex：1 2 100 -- 城市 1 2 之间修建高铁成本为 100，那么的话转换为 map 存储 1-2
Map<String, Integer> costMap = new HashMap<>();
for (int[] cost : costs) {
int city1 = cost[0];
int city2 = cost[1];
int fee = cost[2];
String key = city1 < city2 ? city1 + "-" + city2 : city2 + "-" + city1;
costMap.put(key, fee);
}
// 定义需要输出的结果变量.
int ans = 0;
// 首先处理必建的高铁费用
for (int[] mustCity : mustCities) {
String key = mustCity[0] < mustCity[1] ? mustCity[0] + "-" + mustCity[1] : mustCity[1] + "-" + mustCity[0];
ans += costMap.get(key);
// 将必建的高铁纳入到同一连通分量中.
union.union(mustCity[0], mustCity[1]);
}
if (union.count == 1) {
// 必建高铁已经满足所有城市通车了，那么直接输出结果.
System.out.println(ans);
return;
}
// 如果不行，这个时候按照最小生成树的算法 kruskal 算法
// 将高铁线 成本按照成本费用（即，边的权重） 进行升序
Arrays.sort(costs, (a, b) -> a[2] - b[2]);
// 遍历排序后的成本列表，每一次得到的都是最小权重
for (int[] cost : costs) {
int city1 = cost[0], city2 = cost[1], fee = cost[2];
// 这里需要判断当前 对应城市是否应该修建高铁
// 判断城市是否已经处于连通分量中了，如果存在证明当前城市之间已经可以通高铁了
if(union.find(city1) != union.find(city2)) {
// 不存在，则修建高铁.
union.union(city1, city2);
ans += fee;
}
if(union.count == 1) {
// 表明所有城市互通了（处于同一连通分量）
break;
}
}
if(union.count > 1) {
System.out.println(-1);
}
if(union.count == 1) {
System.out.println(ans);
}
}
public static int minKey(int[] keys, boolean[] visited, int v) {
// 遍历 key 数组使用， min 记录最小的权重值， min_index 记录最小权值关联的顶点.
int min = Integer.MAX_VALUE, min_index = 0;
// 遍历 key 数组 v：顶点数
for (int i = 0; i < v; i++) {
// 如果当前顶点被选择，且对应的权重值小于 min 值， visited = false 表示当前顶点没有访问过.
if (!visited[i] && keys[v] < min) {
// 更新 min 的值，并记录该顶点的位置.
min = keys[i];
min_index = i;
}
}
// 返回最小权值的顶点的位置.
return min_index;
}
}
class UnionFindSet {
int[] parent;
int count;
public UnionFindSet(int n) {
count = n;
parent = new int[n + 1];
for (int i = 0; i < n + 1; i++) {
parent[i] = i;
}
}
/**
* 并查集的 find 方法，查找目标元素 val 所属的集合.
* 该种方法改变了集合形式.
* 初始化--每一个元素属于其本身元素值对应的集合中，所以用 val != parent[val] 来判断
*
* @param val 目标元素 val.
* @return 目标元素所属的集合.
*/
public int findWay1(int val) {
// 查找目标元素 val.
if (val != parent[val]) {
return (parent[val] = findWay1(parent[val]));
}
return val;
}
public int find(int val) {
while (val != parent[val]) {
val = parent[val];
}
return val;
}
/**
* 并查集--快速合并.
*
* @param x 待合并元素 x.
* @param y 待合并元素 y.
*/
public void union(int x, int y) {
// 拿到 x 所属的集合编号
int xFa = find(x);
// 拿到 y 所属的集合编号
int yFa = find(y);
if (xFa != yFa) {
// 如果 x y 所属的集合编号不一致，那么合并它们
// 将集合 y 合并到集合 x
parent[yFa] = xFa;
this.count--;
}
}
}标签：val,int,城市,高铁,union,修建,最优 From： https://blog.51cto.com/u_16079703/7023683