最小生成树
给定一个无向图，在图中选择若干条边把图的所有节点连起来。要求边长之和最小。在图论中，叫做求最小生成树。
prim算法
prim 算法采用的是一种贪心的策略。
每次将离连通部分的最近的点和点对应的边加入的连通部分，连通部分逐渐扩大，最后将整个图连通起来，并且边长之和最小。
prim算法的贪心策略为什么是正确的？
当我们循环到某一部中，当前的连通块为图中绿色虚线内部分，离连通部分的最近的点和点对应的边如下图所示。
假设最小生成树中不包含这条边，那么为了最后保证联通，当前该点一定会通过其他路径与该连通块连起来，假设通过下图中红色路径。
红色路径中一定存在下图中橙色两个点，两点间存在一条边，因为灰色两点间边长一定不大于橙色两点间边长，否则一开始我们选择出的就不是灰色的这个点，所以我们如果把橙色两点间的边删掉，换做灰色两个点的连接，同样可以保持联通，并且一定不会得到更差的结果，也正因此肯证明prim算法贪心策略的正确性，每次将离连通部分的最近的点和点对应的边加入的连通部分。
kruskal算法
将所有边按照边权升序排序，枚举每条边 (a,b)，如果这两个点不连通则把这条边加入最小生成树。
kruskal算法的正确性证明
如下图所示，绿色部分分别是两个连通块，当我们枚举到某一步时，存在一条边可以联通这两个连通块。
我们假设最小生成树中不包含这一条边，那么为了保证这两个连通块最后能够联通，那么这两个点最后肯定会通过其他路径连起来，假设通过下图中红色路径相连。
在该红色路线中，一定存在橙色和蓝色点对之间的距离不小于灰色点对之间的距离，因为在我们枚举到灰色点对时，橙色点对和蓝色点对之间还没联通，并且此时我们没有选择这两条边。所以该我们把灰色点对之间的边去替换掉橙色点对或者蓝色点对一定可以得到不差于当前的答案，也正因此我们把灰色点对联通是最优的。
acwing1140.最短网络
最短路算法裸题
#include <iostream>
#include <cstring>
using namespace std;
const int N = 110;
int n;
int g[N][N];
int dist[N];
bool st[N];
int prim()
{int res = 0;memset(dist, 0x3f, sizeof dist);dist[1] = 0;for (int i = 1; i <= n; i ++ ){int t = -1;for (int j = 1; j <= n; j ++ ){if (!st[j] && (t == -1 || (dist[t] > dist[j])))t = j;}st[t] = 1;res += dist[t];for (int j = 1; j <= n; j ++ )dist[j] = min(dist[j], g[t][j]);}return res;
}
int main()
{cin >> n;for (int i = 1; i <= n; i ++ )for (int j = 1; j <= n; j ++ )cin >> g[i][j];int res = prim();cout << res;return 0;
}
acwing1141.局域网
我们将除去一些连线，使得网络中没有回路且不影响连通性（即如果之前某两个点是连通的，去完之后也必须是连通的），所以在我们去掉回路之后得到的是一个生成森林，在前面我们证明了kruskal算法求出一个最小生成树的结果一定是最优的，我们可以用相同的方法证明kruskal只进行到一半，求出的最小生成森林也是最优的。另外本题要求我们求的是需要删除的边长度最大值，那么我们在枚举边时只需要每次将不需要的边的长度加到答案里便可。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110, M = 210;
struct Edge{int a, b, w;bool operator< (const Edge &t){return w < t.w;}
}e[M];
int fa[N];
int n, m;
int find(int a)
{return fa[a] == a ? a : fa[a] = find(fa[a]);
}
int main()
{cin >> n >> m;for (int i = 1; i <= m; i ++ ){int a, b, w;cin >> a >> b >> w;e[i] = {a, b, w};}for (int i = 1; i <= n; i ++ ) fa[i] = i;int res = 0;sort(e + 1, e + m + 1);for (int i = 1; i <= m; i ++ ){int a = e[i].a, b = e[i].b, w = e[i].w;if (find(a) != find(b)) fa[fa[a]] = b;else res += w;}cout << res;return 0;
}acwing1142.繁忙的都市
1．改造的那些道路能够把所有的交叉路口直接或间接的连通起来。
2．在满足要求1的情况下，改造的道路尽量少。
3．在满足要求1、2的情况下，改造的那些道路中分值最大值尽量小。
首先很显然，为了将所有的边都连通起来，我们改造的道路数为n-1，即一棵生成树，另外本题要求道路中分值最大值尽量小，即求最小瓶颈生成树，而一般的最小生成树问题要求的时边权之和最小。我们可以证明一颗最小生成树一定是最小瓶颈生成树，证明方式和我们一开始最小生成树的证明相同，所以我们可以直接用最短路算法来做，枚举到的长度最长的边就是答案。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 310, M = 8010;
struct Edge{int a, b, w;bool operator< (const Edge &t) const{return w < t.w;}
}e[M];
int fa[N];
int n, m;
int find(int a)
{return fa[a] == a ? a : fa[a] = find(fa[a]);
}
int main()
{cin >> n >> m;for (int i = 1; i <= n; i ++ )fa[i] = i;for (int i = 1; i <= m; i ++ ){int a, b, c;cin >> a >> b >> c;e[i] = {a, b, c};}int res = 0;sort(e + 1, e + m + 1);for (int i = 1; i <= m; i ++ ){int a = find(e[i].a), b = find(e[i].b), w = e[i].w;if (a != b){fa[a] = b;res = w;}}cout << n - 1 << " " << res;return 0;
}
acwing1143.联络员
本题图中存在一些固定的边，要求我们增加一些新的边来让节点之间联通。
我们可以利用Kruskal，算法，思考一下，既然第1类边是必须选择的，那我们在读入的时候就直接把所有第1类边的权值加到我们的总边权中，并将它们统计到判断图是否连通的并查集里，然后照常做Kruskal就行。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2010, M = 10010;
struct Edge{int a, b, w;bool operator< (const Edge &t) const{return w < t.w;}
}e[M];
int fa[N];
int n, m;
int find(int a)
{return fa[a] == a ? a : fa[a] = find(fa[a]);
}
int main()
{cin >> n >> m;int k = 0;for (int i = 1; i <= n; i ++ )fa[i] = i;int res = 0;while (m -- ){int a, b, w, type;cin >> type >> a >> b >> w;if (type == 1){res += w;fa[find(a)] = find(b);}else e[++ k] = {a, b, w};}sort(e + 1, e + k + 1);for (int i = 1; i <= k; i ++ ){int a = find(e[i].a), b = find(e[i].b), w = e[i].w;if (a != b){res += w;fa[a] = b;}}cout << res;return 0;
}
acwing1144.连接格点
本题和上一题的核心思想是完全一样的，只不过本题涉及到了网格图和二维转一维，数据处理会稍微麻烦一些。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010, M = N * N * 2, K = N * N;
int g[N][N];
int fa[N];
struct Edge{int a, b, w;bool operator< (const Edge &t) const{return w < t.w;}
}e[M];
int n, m;
int cnt = 0;
int find(int a)
{fa[a] == a ? a : fa[a] = find(fa[a]);
}
void get_edges()
{int dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0}, dw[] = {2, 1, 2, 1};for (int i = 1; i <= n; i ++ ){for (int j = 1; j <= m; j ++ ){for (int u = 2; u <= 3; u ++ ){int x = i + dx[u], y = j + dy[u];if (x == n + 1 || y == m + 1) continue;int a = g[i][j], b = g[x][y];e[++ cnt] = {a, b, dw[u]};}}}
}
int main()
{cin >> n >> m;int x1, y1, x2, y2;for (int i = 1; i <= n; i ++ )for (int j = 1; j <= n; j ++ )g[i][j] = ++ cnt;cnt = 0;get_edges();for (int i = 1; i <= n * m; i ++ )fa[i] = i;while (cin >> x1 >> y1 >> x2 >> y2){int a = g[x1][y1], b= g[x2][y2];a = find(a), b = find(b);fa[a] = b;}int res = 0;sort(e + 1, e + cnt + 1);for (int i = 1; i <= cnt; i ++ ){int a = find(e[i].a), b = find(e[i].b), w = e[i].w;if (a != b){fa[a] = b;res += w;}}cout << res;return 0;
}
最小生成树扩展应用
