acwing算法提高之图论--最小生成树的扩展应用

1 介绍

本专题用来记录使用最小生成树算法（prim或kruskal）解决的扩展题目。

2 训练

题目1：1146新的开始

C++代码如下，

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 310, INF = 0x3f3f3f3f3;
int n, m;
int g[N][N];
int d[N];
bool st[N];void prim() {memset(d, 0x3f, sizeof d);int res = 0;for (int i = 0; i < n + 1; ++i) {int t = -1;for (int j = 0; j <= n; ++j) {if (!st[j] && (t == -1 || d[t] > d[j])) {t = j;}}st[t] = true;if (i) res += d[t];for (int j = 0; j <= n; ++j) {if (d[j] > g[t][j]) {d[j] = g[t][j];}}}cout << res << endl;return;
}int main() {cin >> n;memset(g, 0, sizeof g);for (int i = 1; i <= n; ++i) {int t;cin >> t;g[0][i] = t;g[i][0] = t;}for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n; ++j) {cin >> g[i][j];}}prim();return 0;   
}

题目2：1145北极通讯网络

C++代码如下，

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>using namespace std;typedef pair<int, int> PII;const int N = 510, M = N * N;
int n, k;
vector<PII> points;
int p[N];struct Edge {int a, b;double w;bool operator< (const Edge &W) const {return w < W.w;}
}edges[M];int find(int x) {if (p[x] != x) p[x] = find(p[x]);return p[x];
}double compute_dis(int i, int j) {int x1 = points[i].first, y1 = points[i].second;int x2 = points[j].first, y2 = points[j].second;double d = double(x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);d = sqrt(d);return d;
}int main() {cin >> n >> k;for (int i = 0; i < n; ++i) {int x, y;cin >> x >> y;points.emplace_back(x,y);}for (int i = 0; i < n; ++i) p[i] = i;int m = 0;for (int i = 0; i < n; ++i) {for (int j = i + 1; j < n; ++j) {double w = compute_dis(i, j);edges[m] = {i, j, w};m += 1;}}sort(edges, edges + m);double res = 0.0;int cnt = n; //连通块的个数for (int i = 0; i < m; ++i) {int a = edges[i].a, b = edges[i].b;double w = edges[i].w;a = find(a);b = find(b);if (cnt == k) {break;}if (a != b) {p[a] = b;cnt--;res = w;}}printf("%.2lf\n", res);return 0;
}

题目3：346走廊泼水节

C++代码如下，

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 6010;
int n, m;
int p[N], ms[N];
struct Edge {int a, b, w;bool operator< (const Edge &W) const {return w < W.w;}
}edges[N];int find(int x) {if (p[x] != x) p[x] = find(p[x]);return p[x];
}int main() {int T;cin >> T;while (T--) {cin >> n;for (int i = 0; i < n - 1; ++i) {cin >> edges[i].a >> edges[i].b >> edges[i].w;}for (int i = 1; i <= n; ++i) p[i] = i, ms[i] = 1;sort(edges, edges + n - 1);int res = 0;for (int i = 0; i < n - 1; ++i) {int a = edges[i].a, b = edges[i].b, w = edges[i].w;a = find(a);b = find(b);if (a != b) {res += (ms[a] * ms[b] - 1) * (w + 1);p[a] = b;ms[b] += ms[a];}}cout << res << endl;}return 0;
}

题目4：1148秘密的牛奶运输

C++代码如下，

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;typedef long long LL;const int N = 510, M = 10010;
int n, m;
struct Edge {int a, b, w;bool f;bool operator< (const Edge &W) const {return w < W.w;}
}edges[M];
int p[N];
int dist1[N][N], dist2[N][N];
int h[N], e[N * 2], w[N * 2], ne[N * 2], idx;void add(int a, int b, int c) {e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}int find(int x) {if (p[x] != x) p[x] = find(p[x]);return p[x];
}void dfs(int u, int fa, int maxd1, int maxd2, int d1[], int d2[]) {d1[u] = maxd1, d2[u] = maxd2;for (int i = h[u]; ~i; i = ne[i]) {int j = e[i];if (j != fa) {int td1 = maxd1, td2 = maxd2;if (w[i] > td1) td2 = td1, td1 = w[i];else if (w[i] < td1 && w[i] > td2) td2 = w[i];dfs(j, u, td1, td2, d1, d2);}}return;
}int main() {scanf("%d%d", &n, &m);memset(h, -1, sizeof h);for (int i = 0; i < m; ++i) {int a, b, w;scanf("%d%d%d", &a, &b, &w);edges[i] = {a, b, w};}sort(edges, edges + m);for (int i = 1; i <= n; ++i) p[i] = i;LL sum = 0;for (int i = 0; i < m; ++i) {int a = edges[i].a, b = edges[i].b, w = edges[i].w;int pa = find(a), pb = find(b);if (pa != pb) {p[pa] = pb;sum += w;add(a, b, w), add(b, a, w);edges[i].f = true;}}for (int i = 1; i <= n; ++i) dfs(i, -1, -1e9, -1e9, dist1[i], dist2[i]);LL res = 1e18;for (int i = 0; i < m; ++i) {if (!edges[i].f) {int a = edges[i].a, b = edges[i].b, w = edges[i].w;LL t;if (w > dist1[a][b]) {t = sum + w - dist1[a][b];} else if (w > dist2[a][b]) {t = sum + w - dist2[a][b];}res=  min(res, t);}}printf("%lld\n", res);return 0;
}