<= 求赞qwq,码字不易,你的支持是我写作的动力
宣传一下算法提高课题解合集
1140.最短网络
农夫约翰被选为他们镇的镇长!
他其中一个竞选承诺就是在镇上建立起互联网,并连接到所有的农场。
约翰已经给他的农场安排了一条高速的网络线路,他想把这条线路共享给其他农场。
约翰的农场的编号是1,其他农场的编号是 $2 \sim n$。
为了使花费最少,他希望用于连接所有的农场的光纤总长度尽可能短。
你将得到一份各农场之间连接距离的列表,你必须找出能连接所有农场并使所用光纤最短的方案。
输入格式
第一行包含一个整数 $n$,表示农场个数。
接下来 $n$ 行,每行包含 $n$ 个整数,输入一个对角线上全是 0 的对称矩阵。
其中第 $x + 1$ 行 $y$ 列的整数表示连接农场 $x$ 和农场 $y$ 所需要的光纤长度。
输出格式
输出一个整数,表示所需的最小光纤长度。
数据范围
$3 \le n \le 100$
每两个农场间的距离均是非负整数且不超过 $100000$。
输入样例:
4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0
输出样例:
28
算法:kruscal
克鲁斯卡尔算法是求连通网的最小生成树的另一种方法。与普里姆算法不同,它的时间复杂度为 $O(eloge)$(e为网中的边数),所以,适合于求边稀疏的网的最小生成树
这道题就是 $kruscal$ 模板题,思路就不多讲了
$kruscal$ 算法:
1、基本思想:贪心思想,按照边权升序排序;
2、按照边权从小到大枚举边,然后每次每次判断枚举的边所连接的两点是否已经联通,如果已经联通,则跳过这条边,否则将这条边算入最小生成树,并将两个点所在的集合联通。
其中判断是否联通以及合并操作,可以用数据结构并查集来维护
具体细节见代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 100009;
struct node
{
int x, y, z;
//x 是起点,y 是终点,z 是权重
bool operator <(const node &e) const
{
return z < e.z;//权重越小越靠前
}
}s[N];//边表,用来存每一条边
int p[N], n, m = 0;
//m 是边的个数
//p[N]是并查集的 parent 数组
//n 是节点个数
int ans;//答案
int find(int x)//并查集查询
{
if(p[x] == x) return x;
else return p[x] = find(p[x]);
}
void merge(int x, int y)//并查集合并
{
p[find(x)] = find(y);
return;
}
void kruscal()//算法核心
{
for(int i = 1;i <= n;++ i) p[i] = i;//初始化
sort(s + 1, s + m + 1);
int cnt = n - 1; ans = 0;
for(int i = 1, x, y, z;i <= m && cnt;++ i)
{
x = s[i].x, y = s[i].y, z = s[i].z;
if(find(x) == find(y)) continue;//不能在同一集合内
cnt --; ans += z;
merge(x, y);
}
return;
}
int main()
{
cin >> n;
for(int i = 1;i <= n;++ i)
for(int j = 1, a;j <= n;++ j)
{
cin >> a; m ++;
s[m] = (node) {i, j, a};//加边
}
kruscal();
cout << ans << endl;
}
最小生成树和最短路的差别是啥
最小生成树构成后所有的点都被连通一共有n-1条边。
而最短路只要从起始点到达目的地走的是最短的路径即可,与所有的点连不连通没有关系。
if(find(x) == find(y)) continue;//不能在同一集合内,这里是不是写错注释了
Kruskal算法可以很好地利用并查集来实现其核心思想,即判断边的两个节点是否在同一个集合中,从而避免形成回路。
在并查集中,每个元素都属于一个集合,并且每个集合有一个代表元素。初始时,每个节点都是一个独立的集合,即每个节点的代表元素是其自身。
Kruskal算法利用并查集的步骤如下:
初始化并查集,将图中的每个节点都作为一个独立的集合,即每个节点的代表元素是其自身。
将图中的所有边按照权重从小到大进行排序。
依次考虑排序后的每条边。
对于当前考虑的边(u, v),查找u和v的代表元素,如果它们的代表元素不同,说明u和v不在同一个集合中,将这条边(u, v)加入最小生成树,并将u和v所在的集合合并(即将其中一个代表元素指向另一个代表元素)。
重复步骤3和步骤4,直到最小生成树中包含了所有的节点(边的数量等于节点数减1)。
通过并查集的合并操作,Kruskal算法能够高效地判断两个节点是否在同一个集合中,从而避免形成回路,并构建出最小生成树。当所有的边都考虑完毕时,最小生成树就构建完成了。
马蜂很好,顶一下