题解 P2820 【局域网】
Suuon_Kanderu
2020-03-03 20:19:56
发个比较详细的吧,这个题解旨在让不会Kruskal的学会它。
- 首先你肯定知道最小生成树是什么: 在一个有$|V|$个点的无相连通图中,连接$|V-1|$个边,且不连通的图叫图的一颗生成树。那最小生成树呢?就是生成树中最小的那一珂。(废话
- 此题和最小生成树有什么关系呢?
1. 我们发现,题目中说**剩下的图中不形成回路**
2. 在不形成回路的基础上 被除取网线的 $f_{i,j}$ 要尽可能大
3. 除取网线的 $f_{i,j}$ 要尽可能大不就是剩下的尽可能小吗?
完美,就是最小生成树
- 学会kruskal
1. 首先我们想,如果要让生成树树最小,那我们就取最小的$|V-1|$条边呗 ~~搞定,结束~~
2. 注意,**剩下的图中不形成回路**
3. 综上,我们在不行成回路的情况下添加边。(很简单
4. 我们注意到,最复杂的就是判断是否形成回路,所以我们接下来要想办法判断加入某边后是否形成环。
- 我们发现,如果形成环,那么必然的,肯定连接的两个点在同一集合内(我语文不好,可能有歧义,姑且允许我这样描述
- 有点抽象,来个图理解一下。
![](https://cdn.luogu.com.cn/upload/image_hosting/tyf37qd7.png)
1. 我们来看这样一个图(图好丑
![](https://cdn.luogu.com.cn/upload/image_hosting/p6982opi.png)
2. 当他被操作成这样时,我们要断开$ 4 - 2$。
3. 4、2在一个集合里,有公共父亲为1
4. 想到是什么了吗?对,就是并查集!
5. 针对不知道并查集的OIer,我解释一下,就是存一下每个节点的最老的祖先,具体实现时递归回溯时标记一下就好了(怎么怪怪的
6. 注: 这里的集合指被选过的节点(又有歧义了,所以我们就只要在 kruscal 时合并集合就可以了。
7. 合并集合的方法,把一个集合最老的祖先换成另一个集合最老的祖先(easy
并查集的code
```
int find(int m)//寻找两个节点是否在一个集合中
{
if(father[m]==m)return m;
else
{
return father[m]=find(father[m]);//标记
}
return father[m];
}
void add(int k,int l){//合并
father[find(k)]=find(l);
}
```
解决,上完整code:
```cpp
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int N = 1e6;
const int Max = 0x7fffffff;
struct side {
int begin,end,cost;
//起点,终点,价值
}a[N];
int fa[N],ans;//并查集
int b;
int n,m;
int find(int x) {
if(x != fa[x])fa[x] = find(fa[x]);
return fa[x];
}
int cmp(side a,side b){
return a.cost < b.cost;
}
void kruskal() {//流程我再详细说一遍
int sum = 0;//选的边有几条
for(int i = 1; i <= m; i++){
int b = a[i].begin,e = a[i].end,c = a[i].cost;
if(find(b) == find(e))continue;//判断是否在一个集合中
fa[find(b)] = find(e);//合并集合
ans += c;//答案
sum++;
if(sum == n-1)break;//如果选的边数 = 节点数-1,说明选好了
}
}
signed main() {
int x,y,z,sum = 0;
cin >> n >>m;
for(int i = 1; i <= n; i++){
fa[i] = i;//并查集初始化,他们最开始父亲肯定是自己
}
for(int i = 1; i <= m; i++) {
scanf("%d%d%d",&x,&y,&z);
a[i].begin = x;
a[i].end = y;
a[i].cost = z;
sum += z; //输入不说了
}
sort(a+1,a+m+1,cmp);//stl大法好(选出最小的
kruskal();
cout << sum - ans << endl;//总数 - 没选的 = 选了的
}
```
我相信像我这样的蒟蒻也能看懂