一本通 3.4.5 最小生成树
1348：【例4-9】城市公交网建设问题
【题目描述】
有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权为在这两个城市之间修建高速公路的造价，研究后发现，这个地图有一个特点，即任一对城市都是连通的。现在的问题是，要修建若干高速公路把所有城市联系起来，问如何设计可使得工程的总造价最少？
【题目分析】
最小生成树模板题，Kruskal算法和Prim算法均可以
【代码实现】
Prim算法
#include<bits/stdc++.h>
using namespace std;struct node {int from;int to;int dis;friend bool operator<(node a, node b) {return a.dis >= b.dis;}
};
vector<node> edge[105];
priority_queue<node> que;
bool vis[105];
int main() {int n, m;cin >> n >> m;for (int i = 1; i <= m; i++) {int x, y, w;cin >> x >> y >> w;edge[x].push_back({x, y, w});edge[y].push_back({y, x, w});}//init priority_queuevis[1] = 1;for (auto e : edge[1]) {que.push(e);}//loop resolvewhile (!que.empty()) {node a = que.top();que.pop();if (!vis[a.to]) {vis[a.to] = 1;cout << a.from << " " << a.to << endl;for (auto e : edge[a.to]){que.push(e);} }}return 0;
}Kruskal算法
#include<bits/stdc++.h>
using namespace std;struct node {int from, to, dis;
};
bool cmp(node &a, node &b) {return a.dis < b.dis;
}
vector<node> edge;
int fa[105];int find(int a) {return fa[a] == a ? a : fa[a] = find(fa[a]);
}
int main() {int n, m;cin >> n >> m;for (int i = 1; i <= n; i++) {fa[i] = i;}for (int i = 1; i <= m; i++) {int x, y, w;cin >> x >> y >> w;edge.push_back({x, y, w});edge.push_back({y, x, w});}sort(edge.begin(), edge.end(), cmp);for (auto e : edge) {int from = find(e.from);int to = find(e.to);if (from != to) {cout << e.from << " " << e.to << endl;fa[from] = to ;}}return 0;
}1349：【例4-10】最优布线问题
【题目描述】
学校有n台计算机，为了方便数据传输，现要将它们用数据线连接起来。两台计算机被连接是指它们有数据线连接。由于计算机所处的位置不同，因此不同的两台计算机的连接费用往往是不同的。
当然，如果将任意两台计算机都用数据线连接，费用将是相当庞大的。为了节省费用，我们采用数据的间接传输手段，即一台计算机可以间接的通过若干台计算机（作为中转）来实现与另一台计算机的连接。
现在由你负责连接这些计算机，任务是使任意两台计算机都连通（不管是直接的或间接的）。
【题目分析】
最小生成树模板题，Kruskal算法和Prim算法均可
【代码实现】
Prim算法
#include <bits/stdc++.h>
#define MAXN 101
using namespace std;const int inf = 0x3f3f3f3f;bool vis[MAXN];
int dis[MAXN], e[MAXN][MAXN];
int ans = 0;
int n, m;int main() {//input data//clock_t s = clock();//initcin >> n;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){scanf("%d",&e[i][j]); }}for (int i = 0; i <= n; i++) {dis[i]=inf;}dis[1] = 0;for (int i = 1; i <= n; i++) {int k = 0;for (int j = 1; j <= n; j++) { //寻找与当前构造完的生成树最近的点if (vis[j]) continue;if (dis[j] < dis[k]) k = j;}ans += dis[k];vis[k] = true;for (int j = 1; j <= n; j++) { //更新其他点到生成树的距离if (e[k][j] < dis[j]) {dis[j] = e[k][j];}}}cout<<ans;//output time//cout <<endl<< clock() - s<<endl;return 0;
}1350：【例4-11】最短网络(agrinet)
【题目描述】
农民约翰被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了用最小的消费，他想铺设最短的光纤去连接所有的农场。你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。每两个农场间的距离不会超过100000100000。
【题目分析】
最小生成树模板题，Kruskal算法和Prim算法均可
【代码实现】
Prim算法
#include <bits/stdc++.h>
#define MAXN 101
using namespace std;const int inf = 0x3f3f3f3f;bool vis[MAXN];
int dis[MAXN], e[MAXN][MAXN];
int ans = 0;
int n, m;int main() {cin >> n;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){scanf("%d",&e[i][j]); }}for (int i = 0; i <= n; i++) {dis[i]=inf;}dis[1] = 0;for (int i = 1; i <= n; i++) {int k = 0;for (int j = 1; j <= n; j++) { //寻找与当前构造完的生成树最近的点if (vis[j]) continue;if (dis[j] < dis[k]) k = j;}ans += dis[k];vis[k] = true;for (int j = 1; j <= n; j++) { //更新其他点到生成树的距离if (e[k][j] < dis[j]) {dis[j] = e[k][j];}}}cout<<ans;return 0;
}1351：【例4-12】家谱树
【题目描述】
有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。
给出每个人的孩子的信息。
输出一个序列，使得每个人的后辈都比那个人后列出。
【题目分析】
拓扑排序模板题
方法1：移除入度为0的点，并将相邻点的入度减1，依次循环直到所有点都被输出
方法2：对所有的点进行深搜，在每个点返回时加入栈，搜索完成后依次弹出点
【代码实现】
方法1：
#include <bits/stdc++.h>using namespace std;
const int maxn = 1001;
int n;
vector<int> p[maxn];
int indeg[maxn];
int vis[maxn];
queue<int> Q;
int main() {cin >> n ;for (int i = 1; i <= n; i++) {int x;while (cin >> x, x != 0) {p[i].push_back(x);indeg[x]++;}}for (int i = 1; i <= n; i++) { //找到起点if (indeg[i] == 0) Q.push(i);}while (!Q.empty()) {int u = Q.front();Q.pop();cout << u << " ";for (int i = 0; i < (int ) p[u].size(); i++) { //依次找后续节点if (--indeg[p[u][i]] == 0)Q.push(p[u][i]);}}return 0;
}方法2：
#include <bits/stdc++.h>using namespace std;vector<int> p[105];
stack<int> sta;
bool vis[105];
void dfs(int x) {for (auto e : p[x]) {if (vis[e]) continue;vis[e] = 1;dfs(e);}sta.push(x);
}
int main() {//input dataint n;cin >> n;for (int i = 1; i <= n; i++) {int x;while (cin >> x, x != 0) p[i].push_back(x);}for (int i = 1; i <= n; i++) {if (!vis[i]) vis[i] = 1, dfs(i);}while (!sta.empty()) cout << sta.top() << " ", sta.pop();return 0;
}1391：局域网(net)
【题目描述】
某个局域网内有n(n≤100)台计算机，由于搭建局域网时工作人员的疏忽，现在局域网内的连接形成了回路，我们知道如果局域网形成回路那么数据将不停的在回路内传输，造成网络卡的现象。因为连接计算机的网线本身不同，所以有一些连线不是很畅通，我们用f(i,j)表示i,j之间连接的畅通程度(f(i,j)≤1000)，f(i,j)值越小表示i,j之间连接越通畅，f(i,j)为00表示i,j之间无网线连接。现在我们需要解决回路问题，我们将除去一些连线，使得网络中没有回路，并且被除去网线的Σf(i,j)最大，请求出这个最大值。
【题目分析】
使得网络中没有回路，并且被除去网线的Σf(i,j)最大，即留下的网线可以生成一个最小生成树，将所有网线的权值相加减去最小生成树的权值，得到最大的移除权值。
算法实现：Kruskal算法或者Prim算法求解最小生成树的权值和
【代码实现】
#include <bits/stdc++.h>using namespace std;
const int maxn = 1001;
struct Edges {int u;int v;int w;
} edge[maxn * 50];
inline bool cmp(const Edges &a, const Edges &b) {return a.w < b.w;
}int n, m;
int father[maxn];
int find(int x) {if (father[x] != x)father[x] = find(father[x]);return father[x];
}
int ans = 0;
int main() {//input data//clock_t s = clock();int sum = 0;cin >> n >> m;for (int i = 1; i <= m; i++) {cin >> edge[i].u >> edge[i].v >> edge[i].w;sum += edge[i].w;}sort(edge + 1, edge + m + 1, cmp);for (int i = 1; i <= n; i++) {father[i] = i;}int _count = 0;for (int i = 1; i <= m; i++) {int fa_u = find(edge[i].u);int fa_v = find(edge[i].v);if (fa_u != fa_v) {ans += edge[i].w;father[fa_u] = fa_v;_count++;if (_count >= n - 1) break;}}cout << sum - ans;//output time//cout <<endl<< clock() - s<<endl;return 0;
}1392：繁忙的都市(city)
【题目描述】
城市C是一个非常繁忙的大都市，城市中的道路十分的拥挤，于是市长决定对其中的道路进行改造。城市C的道路是这样分布的：城市中有n个交叉路口，有些交叉路口之间有道路相连，两个交叉路口之间最多有一条道路相连接。这些道路是双向的，且把所有的交叉路口直接或间接的连接起来了。每条道路都有一个分值，分值越小表示这个道路越繁忙，越需要进行改造。但是市政府的资金有限，市长希望进行改造的道路越少越好，于是他提出下面的要求：
1．改造的那些道路能够把所有的交叉路口直接或间接的连通起来。
2．在满足要求1的情况下，改造的道路尽量少。
3．在满足要求1、2的情况下，改造的那些道路中分值最大值尽量小。
作为市规划局的你，应当作出最佳的决策，选择那些道路应当被修建。
【题目分析】
根据题意：将所有交叉路口直接或间接的连接起来，并使得所有路口的分值之和最小，就是求连接所有交叉路口的最小生成树。
算法实现：Kruskal算法或者Prim算法求解最小生成树的权值和
【代码实现】
#include <bits/stdc++.h>using namespace std;
const int maxn = 1001;
struct Edges {int u;int v;int w;
} edge[maxn * 50];
inline bool cmp(const Edges &a, const Edges &b) {return a.w < b.w;
}int n, m;
int father[maxn];
int find(int x) {if (father[x] != x)father[x] = find(father[x]);return father[x];
}
int ans = 0;
int main() {//input data//clock_t s = clock();int sum = 0;cin >> n >> m;for (int i = 1; i <= m; i++) {cin >> edge[i].u >> edge[i].v >> edge[i].w;sum += edge[i].w;}sort(edge + 1, edge + m + 1, cmp);for (int i = 1; i <= n; i++) {father[i] = i;}int maxw = 0;int _count = 0;for (int i = 1; i <= m; i++) {int fa_u = find(edge[i].u);int fa_v = find(edge[i].v);if (fa_u != fa_v) {maxw = max(maxw, edge[i].w);father[fa_u] = fa_v;_count++;if (_count >= n - 1) break;}}cout << n - 1 << " " << maxw;return 0;
}1393：联络员(liaison)
【题目描述】
Tyvj已经一岁了，网站也由最初的几个用户增加到了上万个用户，随着Tyvj网站的逐步壮大，管理员的数目也越来越多，现在你身为Tyvj管理层的联络员，希望你找到一些通信渠道，使得管理员两两都可以联络（直接或者是间接都可以）。Tyvj是一个公益性的网站，没有过多的利润，所以你要尽可能的使费用少才可以。
目前你已经知道，Tyvj的通信渠道分为两大类，一类是必选通信渠道，无论价格多少，你都需要把所有的都选择上；还有一类是选择性的通信渠道，你可以从中挑选一些作为最终管理员联络的通信渠道。数据保证给出的通行渠道可以让所有的管理员联通。
【题目分析】
必选的通信渠道相加，将连接点进行并查集合并，对可选的通讯渠道排序，依次选择可选渠道使得所有点连通，Kruskal算法思想
【代码实现】
#include <bits/stdc++.h>using namespace std;
const int maxn = 2005;
struct Edges {int u;int v;int w;
} edge[maxn * 50];
inline bool cmp(const Edges &a, const Edges &b) {return a.w < b.w;
}int n, m;
int father[maxn];
int find(int x) {if (father[x] != x)father[x] = find(father[x]);return father[x];
}
int ans = 0;
int main() {//input datacin >> n >> m;int index = 0;int _count = 0;for (int i = 1; i <= n; i++) { //init bing cha jifather[i] = i;}for (int i = 1; i <= m; i++) {int x, y, q, w;cin >> q >> x >> y >> w;if (q == 1) { //direct solveans += w;int fa_x = find(x);int fa_y = find(y);if (fa_x != fa_y) {father[fa_y] = fa_x;_count++;}}if (q == 2) { //save dataedge[++index].u = x;edge[index].v = y;edge[index].w = w;}}//sort and add edgessort(edge + 1, edge + index + 1, cmp);for (int i = 1; i <= index; i++) {
// cout << edge[i].w << " ";int fa_u = find(edge[i].u);int fa_v = find(edge[i].v);if (fa_u != fa_v) {ans += edge[i].w;father[fa_v] = fa_u;_count++;if (_count >= n - 1) break;}}//cout answerscout << ans;return 0;
}1394：连接格点(grid)
【题目描述】
有一个M行N列的点阵，相邻两点可以相连。一条纵向的连线花费一个单位，一条横向的连线花费两个单位。某些点之间已经有连线了，试问至少还需要花费多少个单位才能使所有的点全部连通。
【题目分析】
根据已经相连的线，将线的两端点进行并查集合并，枚举竖边将端点并查集合并，费用加1，枚举横边将端点并查集合并，费用加2，输出结果 Kruskal算法思想
【代码实现】
#include <bits/stdc++.h>using namespace std;struct node {int x, y;
};
node fa[1005][1005];node find(node a) {if (a.x == fa[a.x][a.y].x && a.y == fa[a.x][a.y].y) return a;return fa[a.x][a.y] = find(fa[a.x][a.y]);
}
bool merge(node a, node b) {node fa_a = find(a);node fa_b = find(b);if (fa_a.x != fa_b.x || fa_a.y != fa_b.y) {fa[fa_a.x][fa_a.y] = fa_b;return true;}return false;
}
int main() {//input dataint m, n;cin >> m >> n;for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {fa[i][j] = {i, j};}}int sx, sy, fx, fy;while (cin >> sx >> sy >> fx >> fy) {merge({sx, sy}, {fx, fy});}int sum = 0;//先枚举竖边for (int i = 1; i < m; i++) {for (int j = 1; j <= n; j++) {if (merge({i, j}, {i + 1, j})) sum++;}}//再枚举横边for (int i = 1; i <= m; i++) {for (int j = 1; j < n; j++) {if (merge({i, j}, {i, j + 1})) sum += 2;}}cout << sum << endl;return 0;
}
