华为OD机试双机位C卷 - 最优高铁城市修建方案 (C++ Python JAVA JS GO)

最优高铁城市修建方案

2025华为OD机试双机位C卷 - 华为OD上机考试双机位C卷 200分题型

华为OD机试双机位C卷真题目录点击查看: 华为OD机试双机位C卷真题题库目录｜机考题库 + 算法考点详解

题目描述

高铁城市圈对人们的出行、经济的拉动效果明显。每年都会规划新的高铁城市圈建设。

在给定城市数量、可建设高铁的两城市间的修建成本列表、以及结合城市商业价值会固定建设的两城市建高铁。

请你设计算法，达到修建城市高铁的最低成本。注意，需要满足城市圈内城市间两两互联可达(通过其他城市中转可达也属于满足条件）。

输入描述

输入信息包括：

1. 第一行，包含此城市圈中城市的数量、可建设高铁的两城市间修建成本列表数量、必建高铁的城市列表。三个数字用空格间隔。
2. 可建设高铁的两城市间的修建成本列表，为多行输入数据，格式为3个数字，用空格分隔，长度不超过1000。
3. 固定要修建的高铁城市列表，是上面参数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

说明

3 3 1 城市圈数量为3，表示城市id分别为1，2，3

1 2 10 城市1，2间的高铁修建成本为10

1 3 100 城市1，3间的高铁修建成本为100

2 3 50 城市2，3间的高铁修建成本为50

1 3 城市1，3间的高铁必须修建

因为城市1，3间的高铁必须修建，在满足互联的条件下，再增加修建城市1，2间的高铁即可，最低成本为110

题解

思路：最小生成树变形题，这道题由于添加了必选边，适用于使用以边为基础的Kruskal算法。

1. 介绍：Kruskal算法也是基于贪心算法实现。
   • 初始将所有边按照权值进行升序排序。
   • 然后按照顺序选取边，如果边对应的两个端点不属于同一连通分量则直接合并。
   • 判断是否同一连通分量以及合并采用并查集算法作为底层实现。
2. 了解Kruskal算法之后，这道题初始需要额外处理一下必须边，初始将所有必选边的两个端点进行合并，并记录需要的成本。
3. 接下来就是正常的处理逻辑
   • 将所有边按照成本进行升序排序
   • 按照顺序选取边，如果属于必选边则直接跳过。如果边对应的两个端点不属于同一连通分量则直接合并，并增加成本。
4. 按照3的逻辑处理所有边之后，此时判断是否全部连通可借助并查集实现，判断所有节点是否处于同一集合，如果不是输出-1.如果全部属于同一集合则输出上面计算的成本。

c++

#include<iostream> #include<vector> #include<string> #include <utility> #include <sstream> #include<algorithm> #include<cmath> #include<map> #include<climits> #include<set> using namespace std; struct Edge { int u, v, w; }; // 并查集模板 int find(int x, vector<int>& parent) { if (parent[x] != x) parent[x] = find(parent[x], parent); // 路径压缩 return parent[x]; } // 并查集合并模板 void merge(int a, int b, vector<int> &parent) { int rootA = find(a, parent); int rootB = find(b, parent); int newRoot = min(rootA, rootB); parent[rootA] = newRoot; parent[rootB] = newRoot; } int main() { int n, m, k; cin >> n >> m >> k; vector<Edge> edges(m); for (int i = 0; i < m; i++) { cin >> edges[i].u >> edges[i].v >> edges[i].w; } // 保存必建边 set<pair<int, int>> must; for (int i = 0; i < k; i++) { int u, v; cin >> u >> v; // 保证顺序 if (u > v) { swap(u, v); } must.insert({u, v}); } // 初始化并查集 vector<int> parent(n + 1); for (int i = 0; i <= n; i++) { parent[i] = i; } long totalCost = 0; // 先保证必建边连接 for (auto &e : edges) { int u = e.u, v= e.v, w = e.w; int a = min(u, v), b = max(u, v); if (must.count({a, b})) { totalCost += w; merge(a, b, parent); } } // Kruskal逻辑：对边按权值排序 sort(edges.begin(), edges.end(), [](const Edge &a, const Edge &b) { return a.w < b.w; }); for (auto &e : edges) { int u = e.u, v = e.v, w = e.w; int a = min(u, v), b = max(u, v); // 必建边已处理，跳过 if (must.count({a, b})) continue; // 不属于同一连通块，则合并 if (find(a, parent) != find(b, parent)) { totalCost += w; merge(a, b, parent); } } // 判断所有城市是否连接 int root = find(1, parent); for (int i = 2; i <= n; i++) { if (find(i, parent) != root) { cout << -1; return 0; } } cout << totalCost; return 0; }

JAVA

import java.io.*; import java.util.*; /** * 并查集 + Kruskal */ public class Main { static class Edge { int u, v, w; Edge(int u, int v, int w) { this.u = u; this.v = v; this.w = w; } } // 并查集查找（路径压缩） static int find(int x, int[] parent) { if (parent[x] != x) { parent[x] = find(parent[x], parent); } return parent[x]; } // 并查集合并 static void merge(int a, int b, int[] parent) { int rootA = find(a, parent); int rootB = find(b, parent); int newRoot = Math.min(rootA, rootB); parent[rootA] = newRoot; parent[rootB] = newRoot; } public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); int k = Integer.parseInt(st.nextToken()); List<Edge> edges = new ArrayList<>(); for (int i = 0; i < m; i++) { st = new StringTokenizer(br.readLine()); edges.add(new Edge( Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()) )); } // 保存必建边 Set<String> must = new HashSet<>(); for (int i = 0; i < k; i++) { st = new StringTokenizer(br.readLine()); int u = Integer.parseInt(st.nextToken()); int v = Integer.parseInt(st.nextToken()); if (u > v) { int t = u; u = v; v = t; } must.add(u + "#" + v); } int[] parent = new int[n + 1]; for (int i = 1; i <= n; i++) parent[i] = i; long totalCost = 0; // 先处理必建边 for (Edge e : edges) { int a = Math.min(e.u, e.v); int b = Math.max(e.u, e.v); if (must.contains(a + "#" + b)) { totalCost += e.w; merge(a, b, parent); } } // 按照边权值升序 edges.sort(Comparator.comparingInt(o -> o.w)); for (Edge e : edges) { int a = Math.min(e.u, e.v); int b = Math.max(e.u, e.v); if (must.contains(a + "#" + b)) continue; // 直接合并 if (find(a, parent) != find(b, parent)) { totalCost += e.w; merge(a, b, parent); } } // 检查是否连通 int root = find(1, parent); for (int i = 2; i <= n; i++) { if (find(i, parent) != root) { System.out.println(-1); return; } } System.out.println(totalCost); } }

Python

importsys# 并查集查找（路径压缩）deffind(x,parent):ifparent[x]!=x:parent[x]=find(parent[x],parent)returnparent[x]# 并查集合并defmerge(a,b,parent):ra=find(a,parent)rb=find(b,parent)new_root=min(ra,rb)parent[ra]=new_root parent[rb]=new_rootdefmain():data=sys.stdin.read().strip().split()idx=0n=int(data[idx]);idx+=1m=int(data[idx]);idx+=1k=int(data[idx]);idx+=1edges=[]for_inrange(m):u=int(data[idx]);v=int(data[idx+1]);w=int(data[idx+2])idx+=3edges.append((u,v,w))# 必建边集合must=set()for_inrange(k):u=int(data[idx]);v=int(data[idx+1])idx+=2ifu>v:u,v=v,u must.add((u,v))parent=[iforiinrange(n+1)]total_cost=0# 处理必建边foru,v,winedges:a,b=min(u,v),max(u,v)if(a,b)inmust:total_cost+=w merge(a,b,parent)# 按照边权合并edges.sort(key=lambdax:x[2])foru,v,winedges:a,b=min(u,v),max(u,v)if(a,b)inmust:continueiffind(a,parent)!=find(b,parent):total_cost+=w merge(a,b,parent)# 检查连通性root=find(1,parent)foriinrange(2,n+1):iffind(i,parent)!=root:print(-1)returnprint(total_cost)if__name__=="__main__":main()

JavaScript

'use strict';constreadline=require('readline');constrl=readline.createInterface({input:process.stdin,output:process.stdout});letlines=[];rl.on('line',line=>{if(line.trim().length>0){lines.push(line.trim());}});rl.on('close',()=>{letidx=0;// 读取 n, m, kconst[n,m,k]=lines[idx++].split(/\s+/).map(Number);// 读取所有边letedges=[];for(leti=0;i<m;i++){const[u,v,w]=lines[idx++].split(/\s+/).map(Number);edges.push([u,v,w]);}// 读取必建边letmust=newSet();for(leti=0;i<k;i++){let[u,v]=lines[idx++].split(/\s+/).map(Number);if(u>v)[u,v]=[v,u];must.add(u+"#"+v);}// 并查集初始化letparent=Array(n+1);for(leti=1;i<=n;i++){parent[i]=i;}// 并查集查找（路径压缩）functionfind(x){if(parent[x]!==x){parent[x]=find(parent[x]);}returnparent[x];}// 并查集合并functionmerge(a,b){constra=find(a);constrb=find(b);constroot=Math.min(ra,rb);parent[ra]=root;parent[rb]=root;}lettotalCost=0;// 先处理必建边for(const[u,v,w]ofedges){consta=Math.min(u,v);constb=Math.max(u,v);if(must.has(a+"#"+b)){totalCost+=w;merge(a,b);}}// Kruskal：按权值排序edges.sort((a,b)=>a[2]-b[2]);for(const[u,v,w]ofedges){consta=Math.min(u,v);constb=Math.max(u,v);// 必建边跳过if(must.has(a+"#"+b))continue;// 不在同一连通块才合并if(find(a)!==find(b)){totalCost+=w;merge(a,b);}}// 检查是否全连通constroot=find(1);for(leti=2;i<=n;i++){if(find(i)!==root){console.log(-1);return;}}console.log(totalCost);});

Go

packagemainimport("bufio""fmt""os""sort")typeEdgestruct{u,v,wint}// 并查集查找（路径压缩）funcfind(xint,parent[]int)int{ifparent[x]!=x{parent[x]=find(parent[x],parent)}returnparent[x]}// 并查集合并funcmerge(a,bint,parent[]int){ra:=find(a,parent)rb:=find(b,parent)root:=raifrb<ra{root=rb}parent[ra]=root parent[rb]=root}funcmain(){in:=bufio.NewReader(os.Stdin)varn,m,kintfmt.Fscan(in,&n,&m,&k)edges:=make([]Edge,m)fori:=0;i<m;i++{fmt.Fscan(in,&edges[i].u,&edges[i].v,&edges[i].w)}// 必建边集合must:=make(map[[2]int]bool)fori:=0;i<k;i++{varu,vintfmt.Fscan(in,&u,&v)ifu>v{u,v=v,u}must[[2]int{u,v}]=true}parent:=make([]int,n+1)fori:=1;i<=n;i++{parent[i]=i}vartotalCostint64=0// 必建边处理for_,e:=rangeedges{a,b:=e.u,e.vifa>b{a,b=b,a}ifmust[[2]int{a,b}]{totalCost+=int64(e.w)merge(a,b,parent)}}// Kruskal：按照边权升序sort.Slice(edges,func(i,jint)bool{returnedges[i].w<edges[j].w})for_,e:=rangeedges{a,b:=e.u,e.vifa>b{a,b=b,a}ifmust[[2]int{a,b}]{continue}// 直接选取iffind(a,parent)!=find(b,parent){totalCost+=int64(e.w)merge(a,b,parent)}}// 检查连通root:=find(1,parent)fori:=2;i<=n;i++{iffind(i,parent)!=root{fmt.Println(-1)return}}fmt.Println(totalCost)}