<= 求赞qwq,码字不易,你的支持是我写作的动力
宣传一下算法提高课题解合集
1141.局域网
某个局域网内有 $n$ 台计算机和 $k$ 条 双向 网线,计算机的编号是 $1 \sim n$。
由于搭建局域网时工作人员的疏忽,现在局域网内的连接形成了回路,我们知道如果局域网形成回路那么数据将不停的在回路内传输,造成网络卡的现象。
注意:
-
对于某一个连接,虽然它是双向的,但我们不将其当做回路
-
本题中所描述的回路至少要包含两条不同的连接。
-
两台计算机之间最多只会存在一条连接。
-
不存在一条连接,它所连接的两端是同一台计算机。
因为连接计算机的网线本身不同,所以有一些连线不是很畅通,我们用 $f(i,j)$ 表示 $i,j$ 之间连接的畅通程度,$f(i,j)$ 值越小表示 $i,j$ 之间连接越通畅。
现在我们需要解决回路问题,我们将除去一些连线,使得网络中没有回路且不影响连通性(即如果之前某两个点是连通的,去完之后也必须是连通的),并且被除去网线的 $Σf(i,j)$ 最大.
请求出这个最大值。
输入格式
第一行两个正整数 $n, k$。
接下来的 $k$ 行每行三个正整数 $i, j, m$ 表示 $i,j$ 两台计算机之间有网线联通,通畅程度为 $m$。
输出格式
一个正整数,表示被除去网线的 $Σf(i,j)$ 的最大值。
数据范围
$1 \le n \le 100$
$0 \le k \le 200$
$1 \le f(i,j) \le 1000$
观察题目,注意到题目中有一句:我们将除去一些连线,使得网络中没有回路且不影响连通性。所以最后删完后留下的图一定是一棵树。
再观察注意事项:发现这个图没有自环,没有重边(虽然这条件没什么用)
最后看到输出:竟然是求被除去网线的 $Σf(i,j)$ 的最大值。转换一下,意思就是让我们求最小生成树
最小生成树模板和代码中的变量名解释可以参考这篇题解:AcWing 1140.最短网络
所以这道题就是一道 $kruscal$ 板子题,只需求出最小生成树的边权和(模板),再用所有边权的总和减去就行
PS:发现很多大佬都发现了奇奇怪怪的坑点,但是亲测不需要判断
c++ 代码 $O(m log m)$
#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 = 0;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 >> m;
int sum = 0;
for(int i = 1, x, y, z;i <= m;++ i)
{
cin >> x >> y >> z;//输入边
s[i] = (node) {x, y, z};//加边
sum += z;//更新总和
}
kruscal();
cout << sum - ans << endl;
return 0;
}
写prim板子为什么有一个点过不了啊
判断一下是不是孤立的点,dist【i】==INF时不用加进去就行了
最后应该有可能不只有一棵树把, 可能有好几个, 但是克鲁斯卡尔不用去考虑了, prim需要考虑
对,因为原图可能不止有一个连通图