算法学习系列（五十七）：最小生成树应用

本文主要是介绍算法学习系列（五十七）：最小生成树应用，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

引言

在图论中这个最小生成树还是比较的简单的，只有两种算法： $P r im 算法, Kr u s ka l 算法$ 。一般来说稠密图就用 $P r im 算法$ ，稀疏图就用 $Kr u s ka l 算法$ ，另外这个 $P r im 算法$ 和朴素版的 $D ijk s t r a 算法$ 其实是非常的相像的，思想基本也差不多，唯一的区别就是 $d i s t$ 数组的不同，最小生成树中 $d i s t [i]$ 代表点 $i$ 到集合中的距离，而最短路中 $d i s t [i] [j]$ 代表的就是两点之间的最短距离，然后剩下的就是模板了，本章内容也没啥难的，背包问题做累了，先开一个简单的做做，加油吧！

一、最短网络

标签：最小生成树、prim

思路：首先这个一看就是一个最小生成树问题，数据范围和输入给的信息都说明用 $P r im$ 算法，然后的话，基本就是模板了，关于模板可以参考我之前的博客：最小生成树问题。

题目描述：

农夫约翰被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。约翰的农场的编号是1，其他农场的编号是 2∼n。为了使花费最少，他希望用于连接所有的农场的光纤总长度尽可能短。你将得到一份各农场之间连接距离的列表，你必须找出能连接所有农场并使所用光纤最短的方案。输入格式
第一行包含一个整数 n，表示农场个数。接下来 n 行，每行包含 n 个整数，输入一个对角线上全是0的对称矩阵。其中第 x+1 行 y 列的整数表示连接农场 x 和农场 y 所需
要的光纤长度。输出格式
输出一个整数，表示所需的最小光纤长度。数据范围
3≤n≤100每两个农场间的距离均是非负整数且不超过100000。输入样例：
4
0  4  9  21
4  0  8  17
9  8  0  16
21 17 16  0
输出样例：
28

示例代码：

#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 110, INF = 0x3f3f3f3f;int n;
int g[N][N];
int dist[N];
bool st[N];int Prim()
{memset(dist, 0x3f, sizeof dist);int res = 0;for(int i = 0; i < n; ++i){int t = -1;for(int j = 1; j <= n; ++j){if(!st[j] && (t == -1 || dist[j] < dist[t])) t = j;}if(i && dist[t] == INF) return INF;if(i) res += dist[t];st[t] = true;for(int j = 1; j <= n; ++j) dist[j] = min(dist[j], g[t][j]);}return res;
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin >> n;for(int i = 1; i <= n; ++i){for(int j = 1; j <= n; ++j){cin >> g[i][j];}}cout << Prim() << endl;return 0;
}

二、局域网

标签：最小生成树

思路：首先一眼看出来是最小生成树问题，然后就看要求去除的网线和的最大值，那就是求最小生成树了，然后数据范围显示是一个稀疏图，然后我们可以用 $Kr u s ka l$ 算法，这个算法刚好能够知道哪一条边要用哪条不用，不用的就是遍历时形成回路的那条边，然后加起来就行了，也不用其它的一些值，详情见代码。

题目描述：

某个局域网内有 n 台计算机和 k 条 双向 网线，计算机的编号是 1∼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≤n≤1000≤k≤200,1≤f(i,j)≤1000
输入样例：
5 5
1 2 8
1 3 1
1 5 3
2 4 5
3 4 2
输出样例：
8

示例代码：

#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 110, M = 210, INF = 0x3f3f3f3f;int n, m;
int p[N];struct Edge
{int a, b, w;bool operator<(const Edge& other){return w < other.w;}
}edges[M];int find(int x)
{if(x != p[x]) p[x] = find(p[x]);return p[x];
}int Kruskal()
{for(int i = 1; i <= n; ++i) p[i] = i;sort(edges, edges+m);int res = 0;for(int i = 0; i < m; ++i){int a = edges[i].a, b = edges[i].b, w = edges[i].w;a = find(a), b = find(b);if(a != b) p[a] = b;else res += w;}return res;
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin >> n >> m;for(int i = 0; i < m; ++i){int a, b, w; cin >> a >> b >> w;edges[i] = {a,b,w};}cout << Kruskal() << endl;return 0;
}

三、繁忙的都市

标签：最小生成树

思路：由题意得其实就是把路口当作点，然后求最小生成树呢，第一问肯定是 $n - 1$ ，然后第二问可以在选择的点中取最大值即可。这道题的数据范围要用 $P r im$ 算法来做，该算法中 $d i s t [t]$ 就为选的边，取最大值即可。

题目描述：

城市C是一个非常繁忙的大都市，城市中的道路十分的拥挤，于是市长决定对其中的道路进行改造。城市C的道路是这样分布的：城市中有 n 个交叉路口，编号是 1∼n，有些交叉路口之间有道路相连，两个交叉路口之间最多有一条道路相连接。这些道路是 双向 的，且把所有的交叉路口直接或间接的连接起来了。每条道路都有一个分值，分值越小表示这个道路越繁忙，越需要进行改造。但是市政府的资金有限，市长希望进行改造的道路越少越好，于是他提出下面的要求：1．改造的那些道路能够把所有的交叉路口直接或间接的连通起来。2．在满足要求1的情况下，改造的道路尽量少。3．在满足要求1、2的情况下，改造的那些道路中分值最大值尽量小。作为市规划局的你，应当作出最佳的决策，选择哪些道路应当被修建。输入格式
第一行有两个整数 n,m 表示城市有 n 个交叉路口，m 条道路。接下来 m 行是对每条道路的描述，每行包含三个整数u,v,c 表示交叉路口 u 和 v 之间有道路相连，分值为 c。输出格式
两个整数 s,max，表示你选出了几条道路，分值最大的那条道路的分值是多少。数据范围
1≤n≤300,1≤m≤8000,1≤c≤10000
输入样例：
4 5
1 2 3
1 4 5
2 4 7
2 3 6
3 4 8
输出样例：
3 6

示例代码：

#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 310, M = 8010, INF = 0x3f3f3f3f;int n, m;
int g[N][N], dist[N];
bool st[N];
int maxv;void Prim()
{memset(dist, 0x3f, sizeof dist);for(int i = 0; i < n; ++i){int t = -1;for(int j = 1; j <= n; ++j){if(!st[j] && (t == -1 || dist[j] < dist[t])) t = j;}if(i) maxv = max(maxv, dist[t]);  // dist[t]为选的边st[t] = true;for(int j = 1; j <= n; ++j) dist[j] = min(dist[j], g[t][j]);}
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);memset(g, 0x3f, sizeof g);cin >> n >> m;while(m--){int a, b, w; cin >> a >> b >> w;g[a][b] = g[b][a] = min(g[a][b], w);}Prim();cout << n - 1 << " " << maxv << endl;return 0;
}

四、联络员

标签：最小生成树、Kruskal

思路：首先这道题是一个最小生成树问题，然后一看题意，大体的思路就是先把必须选的选一遍，然后对没有选的做一遍最小生成树就行了，看这个数据范围想着用 $P r im$ 算法，但是如果拿邻接矩阵来存的话，标记边就不好标记了，然后又想着如果拿 $Kr u s ka l$ 算法的话，因为算法特性可以知道哪条边是怎样的，时间复杂度为 $m l o g N$ 数据范围也允许，所以就采用 $Kr u s ka l$ 算法了。然后思路就是刚才说过的，先把必选的加进去，然后对于没有选的最一遍 $Kr u s ka l$ 即可。

题目描述：

Tyvj已经一岁了，网站也由最初的几个用户增加到了上万个用户，随着Tyvj网站的逐步壮大，管理员的数目也越来越多，现在你身
为Tyvj管理层的联络员，希望你找到一些通信渠道，使得管理员两两都可以联络（直接或者是间接都可以）。本题中所涉及的通
信渠道都是 双向 的。Tyvj是一个公益性的网站，没有过多的利润，所以你要尽可能的使费用少才可以。目前你已经知道，Tyvj的通信渠道分为两大类，一类是必选通信渠道，无论价格多少，你都需要把所有的都选择上；还有一类是
选择性的通信渠道，你可以从中挑选一些作为最终管理员联络的通信渠道。数据保证给出的通信渠道可以让所有的管理员联通。注意： 对于某两个管理员 u,v，他们之间可能存在多条通信渠道，你的程序应该累加所有 u,v 之间的必选通行渠道。输入格式
第一行两个整数 n，m 表示Tyvj一共有 n 个管理员，有 m 个通信渠道;第二行到 m+1 行，每行四个非负整数，p,u,v,w 当 p=1 时，表示这个通信渠道为必选通信渠道；当 p=2 时，表示这个通信渠道为
选择性通信渠道；u,v,w 表示本条信息描述的是 u，v 管理员之间的通信渠道，u 可以收到 v 的信息，v 也可以收到 u 的信息，w表示费用。输出格式
一个整数，表示最小的通信费用。数据范围
1≤n≤2000,1≤m≤10000
输入样例：
5 6
1 1 2 1
1 2 3 1
1 3 4 1
1 4 1 1
2 2 5 10
2 2 5 5
输出样例：
9

示例代码：

#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 2010, M = 1e4+10, INF = 0x3f3f3f3f;int n, m;
int p[N];struct Edge
{int a, b, w, fg;bool operator<(const Edge& other){return w < other.w;}
}edges[M];int find(int x)
{if(x != p[x]) p[x] = find(p[x]);return p[x];
}int Kruskal()
{for(int i = 1; i <= n; ++i) p[i] = i;sort(edges,edges+m);int res = 0;for(int i = 0; i < m; ++i){int a = edges[i].a, b = edges[i].b, w = edges[i].w, fg = edges[i].fg;a = find(a), b = find(b);if(fg == 1){res += w;p[a] = b;}		}for(int i = 0; i < m; ++i){int a = edges[i].a, b = edges[i].b, w = edges[i].w, fg = edges[i].fg;a = find(a), b = find(b);if(fg == 2 && a != b){res += w;p[a] = b;}		}return res;
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin >> n >> m;for(int i = 0; i < m; ++i){int fg, a, b, w; cin >> fg >> a >> b >> w;edges[i] = {a,b,w,fg};}cout << Kruskal() << endl;return 0;
}