题解 P2820 【局域网】

发个比较详细的吧，这个题解旨在让不会Kruskal的学会它。 - 首先你肯定知道最小生成树是什么： 在一个有$|V|$个点的无相连通图中，连接$|V-1|$个边，且不连通的图叫图的一颗生成树。那最小生成树呢？就是生成树中最小的那一珂。（废话 - 此题和最小生成树有什么关系呢？ 1. 我们发现，题目中说**剩下的图中不形成回路** 2. 在不形成回路的基础上 被除取网线的 $f_{i,j}$ 要尽可能大 3. 除取网线的 $f_{i,j}$ 要尽可能大不就是剩下的尽可能小吗？ 完美，就是最小生成树 - 学会kruskal 1. 首先我们想，如果要让生成树树最小，那我们就取最小的$|V-1|$条边呗 ~~搞定，结束~~ 2. 注意，**剩下的图中不形成回路** 3. 综上，我们在不行成回路的情况下添加边。（很简单 4. 我们注意到，最复杂的就是判断是否形成回路，所以我们接下来要想办法判断加入某边后是否形成环。 - 我们发现，如果形成环，那么必然的，肯定连接的两个点在同一集合内（我语文不好，可能有歧义，姑且允许我这样描述 - 有点抽象，来个图理解一下。  1. 我们来看这样一个图（图好丑  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;//总数 - 没选的 = 选了的 } ``` 我相信像我这样的蒟蒻也能看懂