企业官网建设流程全解析

办公家具 技术支持 东莞网站建设,天元建设集团有限公司设计研究院赵纪峰联系方式,怎么做跳转网站,网站传送门怎么做(新卷,200分)- 5G网络建设#xff08;Java JS Python C#xff09;题目描述现需要在某城市进行5G网络建设#xff0c;已经选取N个地点设置5G基站#xff0c;编号固定为1到N#xff0c;接下来需要各个基站之间使用光纤进行连接以确保基站能互联互通…(新卷,200分)- 5G网络建设Java JS Python C题目描述现需要在某城市进行5G网络建设已经选取N个地点设置5G基站编号固定为1到N接下来需要各个基站之间使用光纤进行连接以确保基站能互联互通不同基站之间假设光纤的成本各不相同且有些节点之间已经存在光纤相连。请你设计算法计算出能联通这些基站的最小成本是多少。注意基站的联通具有传递性比如基站A与基站B架设了光纤基站B与基站C也架设了光纤则基站A与基站C视为可以互相联通。输入描述第一行输入表示基站的个数N其中0 N ≤ 20第二行输入表示具备光纤直连条件的基站对的数目M其中0 M N * (N - 1) / 2从第三行开始连续输入M行数据格式为X Y Z P其中XY 表示基站的编号0 X ≤ N0 Y ≤ NX ≠ YZ 表示在 X、Y之间架设光纤的成本0 Z 100P 表示是否已存在光纤连接0 表示未连接1表示已连接输出描述如果给定条件可以建设成功互联互通的5G网络则输出最小的建设成本如果给定条件无法建设成功互联互通的5G网络则输出 -1用例输入331 2 3 01 3 1 02 3 5 0输出4说明只需要在12以及13基站之间铺设光纤其成本为314输入311 2 5 0输出-1说明3基站无法与其他基站连接输出-1输入331 2 3 01 3 1 02 3 5 1输出1说明23基站已有光纤相连只要在13基站之间铺设光纤其成本为1题目解析下图中虚线代表节点之间可以铺设光纤但是还没有铺设实线表示已经铺好了用例1图示用例2图示用例3图示本题是经典的最小生成树问题生成树概念而在了解最小生成树概念前我们需要先了解生成树的概念在无向连通图中生成树是指包含了全部顶点的极小连通子图。生成树包含原图全部的n个顶点和n-1条边。注意边的数量一定是n-1比如下面无向连通图例子根据生成树概念我们可以基于上面无向连通图产生多个生成树下面举几个生成树例子如上图我们用n-1条橙色边连接了n个顶点。这样就从无向连通图中产生了生成树。为什么生成树只能由n-1条边呢因为少一条边则生成树就无法包含所有顶点。多一条边则生成树就会形成环。而生成树最重要的两个特性就是1、包含所有顶点2、无环最小生成树概念了解了生成树概念后我们就可以进一步学习最小生成树了。我们回头看看无向连通图可以发现每条边都有权重值比如v1-v2权重值是6v3-v6权重值是4。最小生成树指的是生成树中n-1条边的权重值之和最小。那么如何才能准确的找出一个无向连通图的最小生成树呢有两种算法Prim算法和Kruskal算法。Prim算法是基于顶点找最小生成树。Kruskal是基于边找最小生成树。Prim算法首先我们介绍Prim算法我们可以选择无向连通图中的任意一个顶点作为起始点比如我们选v1顶点为起始点从v1顶点出发有三条边我们选择权重最小的1即将v1-v3相连此时我们需要将v1-v3看成一个整体然后继续找这个整体出发的所有边里面的最小的可以发现为最小权重为4因此将v3-v6相连接着将v1-v3-v6看出一个整体找这个整体出发的所有边里面的最小的可以找到最小权重2因此将v6-v4相连但是接下来我们会发现从v1-v3-v6-v4整体出发的所有边里面同时有三个最小权重5那么该如何选择呢其实不难看出如果选择v4-v3或者v4-v1相连则对应的生成树就形成了环结构因此就不符合生成树特性了因此我们只能选择v3-v2。注意如果有多个相同的最小权重边可选并且都不会产生环结构则可以选择其中任意一条边最终得到结果都是最小生成树其实不仅仅在上面遇到相同权重边时需要判断是否形成环在前选择每一条边时都需要判断是否形成环一旦选择的边能够形成环那么我们就应该舍弃它选择第二小的权重边并继续判断。按照上面逻辑我们可以继续找到v1-v2-v3-v4-v6整体出发所有边中的最小权重边3即将v2-v5相连并且连接后不会形成环​​​​​​​此时选择的边数已经达到了n-1条因此可以结束逻辑而现在得到的就是最小生成树。我们可以将这个最小生成数的所有边的权重值之和计算出来为15。上面这种基于顶点的找最小生成树的方式就是Prim算法。关于Prim算法具体实现细节请看代码实现已添加详细注释。Kruskal算法接下来介绍Kruskal算法Kruskal算法要求我们将所有的边按照权重值升序排序因此可得首先我们将权重最小的边v1-v3加入得到下图​​​​​​​接着将下个最小权重2的边v4-v6加入接着继续加最小权重边​​​​​​​此时边数已经达到n-1而刚好这个过程中也没有环的形成因此得到的就是最小生成树。但是这里有巧合因素在里面因为最后一步中最小权重5的边有多条如果并不是v2-v3排在前面呢比如是v1-v4呢可以发现形成了环因此我们应该舍弃这条边继续找剩下的最小权重边。最后总能找到v2-v3。那么判断环的存在就是实现上面Prim算法和Kruskal算法的关键点其实生成树就是一个连通分量初始时生成树这个连通分量只有一个顶点Prim或者两个顶点Kruskal后面会不断合入新的顶点进来来扩大连通分量范围。而连通分量可以使用并查集表示并查集本质就是一个长度为n的数组n为无向图的顶点数数组索引值代表图中某个顶点child数组索引指向的元素值代表child顶点的祖先顶点father。初始时每个child的father都是自己。即初始时默认有n个连通分量。比如 arr [1,1,1,5,5,5] 数组就可以模拟出一个无向图0顶点索引值的祖先是1顶点元素值1顶点索引值的祖先是1顶点元素值2顶点索引值的祖先是1顶点元素值我们可以用father指代一个连通分量。比如上面arr [1,1,1,5,5,5]就有两个连通分量分别是father为1的连通分量和father为5的连通分量。最小生成树中的顶点必然都处于同一个连通分量中因此每加入一个新的顶点child_new我们我们就可以看它的father是否已经是连通分量对应的father如果是则说明顶点child_new其实已经存在于最小生成树中了因此就产生了环比如下面例子​上面右图绿色部分对应连通图中橙色实线则arr变为​上面右图黄色部分对应连通图中黑色实线即v4顶点的father改成v1但是实际上v4的father已经是v1那么此时如果再强行加入的话那么就形成了环。Prim算法和Kruskal算法的适用场景Prim算法是基于节点操作的因此Prim算法适用于节点少边多的情况Kruskal算法是基于边操作的因此Kruskal算法适用于节点多边少的情况。本题解析本题属于最小生成树的变种题区别于板子题本题中主要是存在一些已经关联好的节点。比如下面连通图中2-3是已经连通好的。其实处理起来也很简单对于已经关联了的节点我们可以认为他们之间的边权为0。即上图中2-3虽然边权为5但是由于已经关联好了因此可以认为实际边权为0。这样的话本题就变成最小生成树的板子题了。JS算法源码Prim算法const rl require(readline).createInterface({ input: process.stdin }); var iter rl[Symbol.asyncIterator](); const readline async () (await iter.next()).value; void (async function () { const n parseInt(await readline()); // 基站数量节点数 const m parseInt(await readline()); // 基站对数量边数 // 邻接矩阵, 初始化默认各点之间互不联通即i-j边权无限大 const graph new Array(n 1) .fill(0) .map(() new Array(n 1).fill(Infinity)); for (let i 0; i m; i) { const [x, y, z, p] (await readline()).split( ).map(Number); if (p 0) { // x-y边权为z graph[x][y] z; graph[y][x] z; } else { // 对应已经联通的两点可以理解为边权为0 graph[x][y] 0; graph[y][x] 0; } } function prim() { // 记录最小生成树的边权和 let minWeight 0; // inTree[i] 表示 节点i 是否在最小生成树中 const inTree new Array(n 1).fill(false); // 初始时任选一个节点作为最小生成树的初始节点这里选择节点1 inTree[1] true; // 记录最小生成树中点数量 let inTree_count 1; // dis[i]表示 节点i 到最小生成树集合 的最短距离 // 初始时最小生成树集合中只有节点1因此其他节点到最小生成树的距离其实就是到节点1的距离 const dis new Array(n 1).fill(0).map((_, i) graph[i][1]); // 如果最小生成树中点数量达到n个则结束循环 while (inTree_count n) { // 现在我们需要从未纳入最小生成树的点中找到一个距离最小生成树最近的 let minDis Infinity; // minDis 记录这个最近距离 let nodeIdx 0; // idx 记录距离最小生成树minDis个距离的节点 for (let i 1; i n; i) { // 从未纳入最小生成树的点中找到一个距离最小生成树最近的 if (!inTree[i] dis[i] minDis) { minDis dis[i]; nodeIdx i; } } // 如果nodeIdx 0,则说明未纳入最小生成树的这些点到最小生成树的距离都是Integer.MAX_VALUE即不与最小生成树存在关联 if (nodeIdx 0) { // 则说明当前所有点无法形成最小生成树 return -1; } inTree[nodeIdx] true; // 最小生成树需要纳入最短距离点nodeIdx inTree_count; // 最小生成树中点数量1 minWeight dis[nodeIdx]; // 更新最小生成树的权重和 // dis[i] 初始时记录的是节点i 到 节点1 的距离初始的生成树中只有节点1 // 现在生成树纳入了新节点nodeIdx则我们需要更新一下dis[i]即有可能某些点到最小生成树中的nodeIdx点距离更近 for (let i 1; i n; i) { if (!inTree[i] graph[nodeIdx][i] dis[i]) { // 注意这是一个累进过程初始时dis[i]记录的是节点i到节点1的距离 // 之后最小生成树纳入新点后如果节点i到新点的距离更近则dis[i]就更新为这个更短距离 // 总之dis[i] 记录的是 节点 i 到最小生成树的最短距离 dis[i] graph[nodeIdx][i]; } } } return minWeight; } console.log(prim()); })();Kruskal算法const rl require(readline).createInterface({ input: process.stdin }); var iter rl[Symbol.asyncIterator](); const readline async () (await iter.next()).value; void (async function () { const n parseInt(await readline()); // 基站数量节点数 const m parseInt(await readline()); // 基站对数量边数 const edges []; for (let i 0; i m; i) { // 边起点, 边终点边权重起点和终点是否已关联 const [x, y, z, p] (await readline()).split( ).map(Number); if (p 0) { // 起点和终点未关联 edges.push([x, y, z]); } else { // 起点和终点已关联则关联代价实际为0 edges.push([x, y, 0]); } } function kruskal() { let minWeight 0; // 按照边权升序 edges.sort((a, b) a[2] - b[2]); const ufs new UnionFindSet(n 1); // 最先遍历出来是边权最小的边 for (const [x, y, z] of edges) { // 如果edge.from节点 和 edge.to节点 是同一个连通分量即都在最小生成树中则此时会产生环 // 因此只有当edge.from节点 和 edge.to节点不在同一个连通分量时才能合并纳入最小生成树 if (ufs.find(x) ! ufs.find(y)) { minWeight z; ufs.union(x, y); // 需要注意的是上面初始化并查集的节点数为n1个因此并查集底层fa数组的长度就是n1即索引范围是[0, n]左闭右闭 // 其中0索引是无用的1~n索引对应最小生成树中各个节点如果者n个节点可以变为最小生成树那么1~n节点会被合并为一个连通分量 // 而0索引虽然无用但是也会自己形成一个连通分量因此最终如果能形成最小生成树则并查集中会有两个连通分量 if (ufs.count 2) { return minWeight; } } } return -1; } console.log(kruskal()); })(); // 并查集实现 class UnionFindSet { constructor(n) { this.fa new Array(n).fill(true).map((_, idx) idx); this.count n; // 初始时各站点互不相连互相独立因此需要给n个站点发送广播 } // 查x站点对应的顶级祖先站点 find(x) { while (x ! this.fa[x]) { x this.fa[x]; } return x; } // 合并两个站点其实就是合并两个站点对应的顶级祖先节点 union(x, y) { let x_fa this.find(x); let y_fa this.find(y); if (x_fa ! y_fa) { // 如果两个站点祖先相同则在一条链上不需要合并 this.fa[y_fa] x_fa; // 合并站点即让某条链的祖先指向另一条链的祖先 this.count--; // 一旦两个站点合并则发送广播次数减1 } } }Java算法源码Prim算法import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); // 基站数量节点数 int m sc.nextInt(); // 基站对数量边数 // 邻接矩阵 int[][] graph new int[n 1][n 1]; for (int i 1; i n; i) { for (int j 1; j n; j) { // 初始化默认各点之间互不联通即i-j边权无限大 graph[i][j] Integer.MAX_VALUE; } } for (int i 0; i m; i) { int x sc.nextInt(); int y sc.nextInt(); int z sc.nextInt(); int p sc.nextInt(); if (p 0) { // x-y边权为z graph[x][y] z; graph[y][x] z; } else { // 对应已经联通的两点可以理解为边权为0 graph[x][y] 0; graph[y][x] 0; } } System.out.println(prim(graph, n)); } public static int prim(int[][] graph, int n) { // 记录最小生成树的边权和 int minWeight 0; // inTree[i] 表示 节点i 是否在最小生成树中 boolean[] inTree new boolean[n 1]; // 初始时任选一个节点作为最小生成树的初始节点这里选择节点1 inTree[1] true; // 记录最小生成树中点数量 int inTree_count 1; // dis[i]表示 节点i 到最小生成树集合 的最短距离 int[] dis new int[n 1]; for (int i 1; i n; i) { // 初始时最小生成树集合中只有节点1因此其他节点到最小生成树的距离其实就是到节点1的距离 dis[i] graph[1][i]; } // 如果最小生成树中点数量达到n个则结束循环 while (inTree_count n) { // 现在我们需要从未纳入最小生成树的点中找到一个距离最小生成树最近的 // minDis 记录这个最近距离 int minDis Integer.MAX_VALUE; // idx 记录距离最小生成树minDis个距离的节点 int nodeIdx 0; for (int i 1; i n; i) { // 从未纳入最小生成树的点中找到一个距离最小生成树最近的 if (!inTree[i] dis[i] minDis) { minDis dis[i]; nodeIdx i; } } // 如果nodeIdx 0,则说明未纳入最小生成树的这些点到最小生成树的距离都是Integer.MAX_VALUE即不与最小生成树存在关联 if (nodeIdx 0) { // 则说明当前所有点无法形成最小生成树 return -1; } inTree[nodeIdx] true; // 最小生成树需要纳入最短距离点nodeIdx inTree_count; // 最小生成树中点数量1 minWeight dis[nodeIdx]; // 更新最小生成树的权重和 // dis[i] 初始时记录的是节点i 到 节点1 的距离初始的生成树中只有节点1 // 现在生成树纳入了新节点nodeIdx则我们需要更新一下dis[i]即有可能某些点到最小生成树中的nodeIdx点距离更近 for (int i 1; i n; i) { if (!inTree[i] graph[nodeIdx][i] dis[i]) { // 注意这是一个累进过程初始时dis[i]记录的是节点i到节点1的距离 // 之后最小生成树纳入新点后如果节点i到新点的距离更近则dis[i]就更新为这个更短距离 // 总之dis[i] 记录的是 节点 i 到最小生成树的最短距离 dis[i] graph[nodeIdx][i]; } } } return minWeight; } }Kruskal算法import java.util.Arrays; import java.util.Scanner; public class Main { // 边 static class Edge { int from; // 边起点 int to; // 边终点 int weight; // 边权重 public Edge(int from, int to, int weight) { this.from from; this.to to; this.weight weight; } } public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); // 基站数量节点数 int m sc.nextInt(); // 基站对数量边数 Edge[] edges new Edge[m]; for (int i 0; i m; i) { int x sc.nextInt(); int y sc.nextInt(); int z sc.nextInt(); int p sc.nextInt(); // 如果p1则可以认为x-y边权为0 edges[i] new Edge(x, y, p 0 ? z : 0); } System.out.println(kruskal(edges, n)); } public static int kruskal(Edge[] edges, int n) { int minWeight 0; // 按照边权升序 Arrays.sort(edges, (a, b) - a.weight - b.weight); UnionFindSet ufs new UnionFindSet(n 1); // 最先遍历出来是边权最小的边 for (Edge edge : edges) { // 如果edge.from节点 和 edge.to节点 是同一个连通分量即都在最小生成树中则此时会产生环 // 因此只有当edge.from节点 和 edge.to节点不在同一个连通分量时才能合并纳入最小生成树 if (ufs.find(edge.from) ! ufs.find(edge.to)) { minWeight edge.weight; ufs.union(edge.from, edge.to); // 需要注意的是上面初始化并查集的节点数为n1个因此并查集底层fa数组的长度就是n1即索引范围是[0, n]左闭右闭 // 其中0索引是无用的1~n索引对应最小生成树中各个节点如果者n个节点可以变为最小生成树那么1~n节点会被合并为一个连通分量 // 而0索引虽然无用但是也会自己形成一个连通分量因此最终如果能形成最小生成树则并查集中会有两个连通分量 if (ufs.count 2) { return minWeight; } } } return -1; } } // 并查集 class UnionFindSet { int[] fa; int count; public UnionFindSet(int n) { this.fa new int[n]; this.count n; for (int i 0; i n; i) this.fa[i] i; } public int find(int x) { if (x ! this.fa[x]) { return (this.fa[x] this.find(this.fa[x])); } return x; } public void union(int x, int y) { int x_fa this.find(x); int y_fa this.find(y); if (x_fa ! y_fa) { this.fa[y_fa] x_fa; this.count--; } } }Python算法源码Prim算法import sys # 输入获取 n int(input()) # 基站数量节点数 m int(input()) # 基站对数量边数 # 邻接矩阵, 初始化默认各点之间互不联通即i-j边权无限大 graph [[sys.maxsize for _ in range(n 1)] for _ in range(n 1)] for _ in range(m): x, y, z, p map(int, input().split()) if p 0: # x-y边权为z graph[x][y] z graph[y][x] z else: # 对应已经联通的两点可以理解为边权为0 graph[x][y] 0 graph[y][x] 0 # Prim算法 def prim(): # 记录最小生成树的边权和 minWeight 0 # inTree[i] 表示 节点i 是否在最小生成树中 inTree [False] * (n 1) # 初始时任选一个节点作为最小生成树的初始节点这里选择节点1 inTree[1] True # 记录最小生成树中点数量 inTree_count 1 # dis[i]表示 节点i 到最小生成树集合 的最短距离 # 初始时最小生成树集合中只有节点1因此其他节点到最小生成树的距离其实就是到节点1的距离 dis [0] * (n 1) for i in range(1, n 1): dis[i] graph[1][i] # 如果最小生成树中点数量达到n个则结束循环 while inTree_count n: # 现在我们需要从未纳入最小生成树的点中找到一个距离最小生成树最近的 minDis sys.maxsize # minDis 记录这个最近距离 nodeIdx 0 # idx 记录距离最小生成树minDis个距离的节点 for i in range(1, n1): # 从未纳入最小生成树的点中找到一个距离最小生成树最近的 if not inTree[i] and dis[i] minDis: minDis dis[i] nodeIdx i # 如果nodeIdx 0,则说明未纳入最小生成树的这些点到最小生成树的距离都是Integer.MAX_VALUE即不与最小生成树存在关联 if nodeIdx 0: # 则说明当前所有点无法形成最小生成树 return -1 inTree[nodeIdx] True # 最小生成树需要纳入最短距离点nodeIdx inTree_count 1 # 最小生成树中点数量1 minWeight dis[nodeIdx] # 更新最小生成树的权重和 # dis[i] 初始时记录的是节点i 到 节点1 的距离初始的生成树中只有节点1 # 现在生成树纳入了新节点nodeIdx则我们需要更新一下dis[i]即有可能某些点到最小生成树中的nodeIdx点距离更近 for i in range(1, n1): if not inTree[i] and graph[nodeIdx][i] dis[i]: # 注意这是一个累进过程初始时dis[i]记录的是节点i到节点1的距离 # 之后最小生成树纳入新点后如果节点i到新点的距离更近则dis[i]就更新为这个更短距离 # 总之dis[i] 记录的是 节点 i 到最小生成树的最短距离 dis[i] graph[nodeIdx][i] return minWeight # 算法调用 print(prim())Kruskal算法# 并查集实现 class UnionFindSet: def __init__(self, n): self.fa [i for i in range(n)] self.count n def find(self, x): if x ! self.fa[x]: self.fa[x] self.find(self.fa[x]) return self.fa[x] return x def union(self, x, y): x_fa self.find(x) y_fa self.find(y) if x_fa ! y_fa: self.fa[y_fa] x_fa self.count - 1 # 输入获取 n int(input()) # 基站数量节点数 m int(input()) # 基站对数量边数 edges [] for _ in range(m): # 边起点边终点边权重起点和终点关联代价起点是否已和终点关联 x, y, z, p map(int, input().split()) if p 0: # 起点和终点未关联 edges.append([x, y, z]) else: # 起点和终点已关联则实际关联代价为0 edges.append([x, y, 0]) # kruskal算法 def kruskal(): minWeight 0 # 按照边权升序 edges.sort(keylambda x: x[2]) ufs UnionFindSet(n1) # 最先遍历出来是边权最小的边 for x, y, z in edges: # 如果x节点 和 y节点 是同一个连通分量即都在最小生成树中则此时会产生环 # 因此只有当x节点 和 y节点不在同一个连通分量时才能合并纳入最小生成树 if ufs.find(x) ! ufs.find(y): minWeight z ufs.union(x, y) # 需要注意的是上面初始化并查集的节点数为n1个因此并查集底层fa数组的长度就是n1即索引范围是[0, n]左闭右闭 # 其中0索引是无用的1~n索引对应最小生成树中各个节点如果者n个节点可以变为最小生成树那么1~n节点会被合并为一个连通分量 # 而0索引虽然无用但是也会自己形成一个连通分量因此最终如果能形成最小生成树则并查集中会有两个连通分量 if ufs.count 2: return minWeight return -1 # 算法入口 print(kruskal())C算法源码Prim算法#include stdio.h #include limits.h int n, m; // 基站数量节点数,基站对数量边数 int graph[21][21]; // 邻接矩阵 int prim() { // 记录最小生成树的边权和 int minWeight 0; // inTree[i] 表示 节点i 是否在最小生成树中 int inTree[21] {0}; // 初始时任选一个节点作为最小生成树的初始节点这里选择节点1 inTree[1] 1; // 记录最小生成树中点数量 int inTree_count 1; // dis[i]表示 节点i 到最小生成树集合 的最短距离 int dis[21]; for (int i 1; i n; i) { // 初始时最小生成树集合中只有节点1因此其他节点到最小生成树的距离其实就是到节点1的距离 dis[i] graph[1][i]; } // 如果最小生成树中点数量达到n个则结束循环 while (inTree_count n) { // 现在我们需要从未纳入最小生成树的点中找到一个距离最小生成树最近的 int minDis INT_MAX; // minDis 记录这个最近距离 int nodeIdx 0; // idx 记录距离最小生成树minDis个距离的节点 for (int i 1; i n; i) { // 从未纳入最小生成树的点中找到一个距离最小生成树最近的 if (!inTree[i] dis[i] minDis) { minDis dis[i]; nodeIdx i; } } // 如果nodeIdx 0,则说明未纳入最小生成树的这些点到最小生成树的距离都是Integer.MAX_VALUE即不与最小生成树存在关联 if (nodeIdx 0) { // 则说明当前所有点无法形成最小生成树 return -1; } inTree[nodeIdx] 1; // 最小生成树需要纳入最短距离点nodeIdx inTree_count; // 最小生成树中点数量1 minWeight dis[nodeIdx]; // 更新最小生成树的权重和 // dis[i] 初始时记录的是节点i 到 节点1 的距离初始的生成树中只有节点1 // 现在生成树纳入了新节点nodeIdx则我们需要更新一下dis[i]即有可能某些点到最小生成树中的nodeIdx点距离更近 for (int i 1; i n; i) { if (!inTree[i] graph[nodeIdx][i] dis[i]) { // 注意这是一个累进过程初始时dis[i]记录的是节点i到节点1的距离 // 之后最小生成树纳入新点后如果节点i到新点的距离更近则dis[i]就更新为这个更短距离 // 总之dis[i] 记录的是 节点 i 到最小生成树的最短距离 dis[i] graph[nodeIdx][i]; } } } return minWeight; } int main() { scanf(%d %d, n, m); for (int i 1; i n; i) { for (int j 1; j n; j) { // 初始化默认各点之间互不联通即i-j边权无限大 graph[i][j] INT_MAX; } } for (int i 0; i m; i) { int x, y, z, p; scanf(%d %d %d %d, x, y, z, p); if (p 0) { // x-y边权为z graph[x][y] z; graph[y][x] z; } else { // 对应已经联通的两点可以理解为边权为0 graph[x][y] 0; graph[y][x] 0; } } printf(%d\n, prim()); return 0; }Kruskal算法#include stdio.h #include stdlib.h /** 并查集定义 **/ typedef struct { int *fa; int count; } UFS; UFS *new_UFS(int n) { UFS *ufs (UFS *) malloc(sizeof(UFS)); ufs-fa (int *) malloc(sizeof(int) * n); for (int i 0; i n; i) { ufs-fa[i] i; } ufs-count n; return ufs; } int find_UFS(UFS *ufs, int x) { if (x ! ufs-fa[x]) { ufs-fa[x] find_UFS(ufs, ufs-fa[x]); return ufs-fa[x]; } return x; } void union_UFS(UFS *ufs, int x, int y) { int x_fa find_UFS(ufs, x); int y_fa find_UFS(ufs, y); if (x_fa ! y_fa) { ufs-fa[y_fa] x_fa; ufs-count--; } } /*** 边定义 ***/ typedef struct Edge { int from; // 边起点 int to; // 边终点 int weight; // 边权重 } Edge; int n, m; Edge *edges; int cmp(const void* a, const void* b) { return ((Edge*) a)-weight - ((Edge*) b)-weight; } int kruskal() { int minWeight 0; // 按照边权升序 qsort(edges, m, sizeof(Edge), cmp); UFS* ufs new_UFS(n 1); // 最先遍历出来是边权最小的边 for(int i0; im; i) { int x edges[i].from; int y edges[i].to; int z edges[i].weight; // 如果edge.from节点 和 edge.to节点 是同一个连通分量即都在最小生成树中则此时会产生环 // 因此只有当edge.from节点 和 edge.to节点不在同一个连通分量时才能合并纳入最小生成树 if(find_UFS(ufs, x) ! find_UFS(ufs, y)) { minWeight z; union_UFS(ufs, x, y); // 需要注意的是上面初始化并查集的节点数为n1个因此并查集底层fa数组的长度就是n1即索引范围是[0, n]左闭右闭 // 其中0索引是无用的1~n索引对应最小生成树中各个节点如果者n个节点可以变为最小生成树那么1~n节点会被合并为一个连通分量 // 而0索引虽然无用但是也会自己形成一个连通分量因此最终如果能形成最小生成树则并查集中会有两个连通分量 if(ufs-count 2) { return minWeight; } } } return -1; } int main() { scanf(%d %d, n, m); edges (Edge*) malloc(sizeof(Edge) * m); for (int i 0; i m; i) { int x, y, z, p; scanf(%d %d %d %d, x, y, z, p); edges[i].from x; edges[i].to y; if(p 0) { edges[i].weight z; } else { // 如果p1则可以认为x-y边权为0 edges[i].weight 0; } } printf(%d\n, kruskal()); return 0; }