企业官网建设流程全解析

制作企业网站新闻列表页面网页设计,9 1短视频安装软件,在线直播免费服务器,云虚拟主机搭建wordpress最优高铁城市修建方案 2025华为OD机试双机位C卷 - 华为OD上机考试双机位C卷 200分题型 华为OD机试双机位C卷真题目录点击查看: 华为OD机试双机位C卷真题题库目录#xff5c;机考题库 算法考点详解 题目描述 高铁城市圈对人们的出行、经济的拉动效果明显。每年都会规划新的…最优高铁城市修建方案2025华为OD机试双机位C卷 - 华为OD上机考试双机位C卷 200分题型华为OD机试双机位C卷真题目录点击查看: 华为OD机试双机位C卷真题题库目录机考题库 算法考点详解题目描述高铁城市圈对人们的出行、经济的拉动效果明显。每年都会规划新的高铁城市圈建设。在给定城市数量、可建设高铁的两城市间的修建成本列表、以及结合城市商业价值会固定建设的两城市建高铁。请你设计算法达到修建城市高铁的最低成本。注意需要满足城市圈内城市间两两互联可达(通过其他城市中转可达也属于满足条件。输入描述输入信息包括第一行包含此城市圈中城市的数量、可建设高铁的两城市间修建成本列表数量、必建高铁的城市列表。三个数字用空格间隔。可建设高铁的两城市间的修建成本列表为多行输入数据格式为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,31 2 10城市12间的高铁修建成本为101 3 100城市13间的高铁修建成本为1002 3 50城市23间的高铁修建成本为50满足修建成本最低只需要建设城市12间城市23间的高铁即可城市13之间可通过城市2中转来互联。这样最低修建成本就是60。用例2输入3 3 1 1 2 10 1 3 100 2 3 50 1 3输出110说明3 3 1 城市圈数量为3表示城市id分别为1231 2 10 城市12间的高铁修建成本为101 3 100 城市13间的高铁修建成本为1002 3 50 城市23间的高铁修建成本为501 3 城市13间的高铁必须修建因为城市13间的高铁必须修建在满足互联的条件下再增加修建城市12间的高铁即可最低成本为110题解思路最小生成树变形题这道题由于添加了必选边适用于使用以边为基础的Kruskal算法。介绍Kruskal算法也是基于贪心算法实现。初始将所有边按照权值进行升序排序。然后按照顺序选取边如果边对应的两个端点不属于同一连通分量则直接合并。判断是否同一连通分量以及合并采用并查集算法作为底层实现。了解Kruskal算法之后这道题初始需要额外处理一下必须边初始将所有必选边的两个端点进行合并并记录需要的成本。接下来就是正常的处理逻辑将所有边按照成本进行升序排序按照顺序选取边如果属于必选边则直接跳过。如果边对应的两个端点不属于同一连通分量则直接合并并增加成本。按照3的逻辑处理所有边之后此时判断是否全部连通可借助并查集实现判断所有节点是否处于同一集合如果不是输出-1.如果全部属于同一集合则输出上面计算的成本。c#includeiostream #includevector #includestring #include utility #include sstream #includealgorithm #includecmath #includemap #includeclimits #includeset using namespace std; struct Edge { int u, v, w; }; // 并查集模板 int find(int x, vectorint parent) { if (parent[x] ! x) parent[x] find(parent[x], parent); // 路径压缩 return parent[x]; } // 并查集合并模板 void merge(int a, int b, vectorint 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; vectorEdge edges(m); for (int i 0; i m; i) { cin edges[i].u edges[i].v edges[i].w; } // 保存必建边 setpairint, 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}); } // 初始化并查集 vectorint 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; }JAVAimport 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()); ListEdge 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()) )); } // 保存必建边 SetString 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); } }Pythonimportsys# 并查集查找路径压缩deffind(x,parent):ifparent[x]!x:parent[x]find(parent[x],parent)returnparent[x]# 并查集合并defmerge(a,b,parent):rafind(a,parent)rbfind(b,parent)new_rootmin(ra,rb)parent[ra]new_root parent[rb]new_rootdefmain():datasys.stdin.read().strip().split()idx0nint(data[idx]);idx1mint(data[idx]);idx1kint(data[idx]);idx1edges[]for_inrange(m):uint(data[idx]);vint(data[idx1]);wint(data[idx2])idx3edges.append((u,v,w))# 必建边集合mustset()for_inrange(k):uint(data[idx]);vint(data[idx1])idx2ifuv:u,vv,u must.add((u,v))parent[iforiinrange(n1)]total_cost0# 处理必建边foru,v,winedges:a,bmin(u,v),max(u,v)if(a,b)inmust:total_costw merge(a,b,parent)# 按照边权合并edges.sort(keylambdax:x[2])foru,v,winedges:a,bmin(u,v),max(u,v)if(a,b)inmust:continueiffind(a,parent)!find(b,parent):total_costw merge(a,b,parent)# 检查连通性rootfind(1,parent)foriinrange(2,n1):iffind(i,parent)!root:print(-1)returnprint(total_cost)if__name____main__:main()JavaScriptuse strict;constreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});letlines[];rl.on(line,line{if(line.trim().length0){lines.push(line.trim());}});rl.on(close,(){letidx0;// 读取 n, m, kconst[n,m,k]lines[idx].split(/\s/).map(Number);// 读取所有边letedges[];for(leti0;im;i){const[u,v,w]lines[idx].split(/\s/).map(Number);edges.push([u,v,w]);}// 读取必建边letmustnewSet();for(leti0;ik;i){let[u,v]lines[idx].split(/\s/).map(Number);if(uv)[u,v][v,u];must.add(u#v);}// 并查集初始化letparentArray(n1);for(leti1;in;i){parent[i]i;}// 并查集查找路径压缩functionfind(x){if(parent[x]!x){parent[x]find(parent[x]);}returnparent[x];}// 并查集合并functionmerge(a,b){constrafind(a);constrbfind(b);constrootMath.min(ra,rb);parent[ra]root;parent[rb]root;}lettotalCost0;// 先处理必建边for(const[u,v,w]ofedges){constaMath.min(u,v);constbMath.max(u,v);if(must.has(a#b)){totalCostw;merge(a,b);}}// Kruskal按权值排序edges.sort((a,b)a[2]-b[2]);for(const[u,v,w]ofedges){constaMath.min(u,v);constbMath.max(u,v);// 必建边跳过if(must.has(a#b))continue;// 不在同一连通块才合并if(find(a)!find(b)){totalCostw;merge(a,b);}}// 检查是否全连通constrootfind(1);for(leti2;in;i){if(find(i)!root){console.log(-1);return;}}console.log(totalCost);});Gopackagemainimport(bufiofmtossort)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:raifrbra{rootrb}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;im;i{fmt.Fscan(in,edges[i].u,edges[i].v,edges[i].w)}// 必建边集合must:make(map[[2]int]bool)fori:0;ik;i{varu,vintfmt.Fscan(in,u,v)ifuv{u,vv,u}must[[2]int{u,v}]true}parent:make([]int,n1)fori:1;in;i{parent[i]i}vartotalCostint640// 必建边处理for_,e:rangeedges{a,b:e.u,e.vifab{a,bb,a}ifmust[[2]int{a,b}]{totalCostint64(e.w)merge(a,b,parent)}}// Kruskal按照边权升序sort.Slice(edges,func(i,jint)bool{returnedges[i].wedges[j].w})for_,e:rangeedges{a,b:e.u,e.vifab{a,bb,a}ifmust[[2]int{a,b}]{continue}// 直接选取iffind(a,parent)!find(b,parent){totalCostint64(e.w)merge(a,b,parent)}}// 检查连通root:find(1,parent)fori:2;in;i{iffind(i,parent)!root{fmt.Println(-1)return}}fmt.Println(totalCost)}