「题解」kuangbin 最小生成树

概述

  • POJ-1251 Jungle Roads (水题,%c)
  • POJ-1287 Networking (水)
  • POJ-2031 Building a Space Station (%f浮点数尴尬精度,两球间距离)
  • POJ-2421 Constructing Roads (一些边已建好,简单处理一下)
  • ZOJ-1586 QS Network (处理一下边权)
  • HDU-1233 还是畅通工程 (水)
  • HDU-1875 畅通工程再续 (浮点数,条件连边)
  • HDU-1301 Jungle Roads (重复 -> POJ-1251)
  • POJ-2349 Arctic Network (第 K 大边)
  • POJ-1751 Highways (求最小生成树的边,加 0 权边)
  • UVA-10147 Highways (多组的 POJ-1751) +
  • POJ-1258 Agri-Net (水)
  • POJ-3026 Borg Maze (BFS + Kruskal,用最短路建图,垃圾输入)
  • POJ-1789 Truck History (Prim,Kruskal 超时)
  • POJ-1679 The Unique MST (次小生成树)

代码最后附简单题解

模板

Kruskal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/*
* Kruskal 算法求 MST
*/

#include <string.h>
#include <algorithm>
using namespace std;

const int MAXN = 110; //最大点数
const int MAXM = 10000; //最大边数
int F[MAXN]; //并查集使用
struct Edge {
int u, v, w;
} edge[MAXM]; //存储边的信息,包括起点/终点/权值
int tol; //边数,加边前赋值为 0
void addedge(int u, int v, int w) {
edge[tol].u = u;
edge[tol].v = v;
edge[tol++].w = w;
} //排序函数,讲边按照权值从小到大排序
bool cmp(Edge a, Edge b) { return a.w < b.w; }
int find(int x) {
if (F[x] == -1)
return x;
else
return F[x] = find(F[x]);
} //传入点数,返回最小生成树的权值,如果不连通返回 -1
int Kruskal(int n) {
memset(F, -1, sizeof(F));
sort(edge, edge + tol, cmp);
int cnt = 0; //计算加入的边数

int ans = 0;
for (int i = 0; i < tol; i++) {
int u = edge[i].u;
int v = edge[i].v;
int w = edge[i].w;
int t1 = find(u);
int t2 = find(v);
if (t1 != t2) {
ans += w;
F[t1] = t2;
cnt++;
}
if (cnt == n - 1) break;
}
if (cnt < n - 1)
return -1; //不连通
else
return ans;
}

Prim

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/*
* Prim 求 MST
* 耗费矩阵 cost[][],标号从 0 开始,0∼n-1
* 返回最小生成树的权值,返回 -1 表示原图不连通
*/
#include <string.h>

const int INF = 0x3f3f3f3f;
const int MAXN = 110;
bool vis[MAXN];
int lowc[MAXN];
//点是 0 n-1
int Prim(int cost[][MAXN], int n) {
int ans = 0;
memset(vis, false, sizeof(vis));
vis[0] = true;
for (int i = 1; i < n; i++) lowc[i] = cost[0][i];
for (int i = 1; i < n; i++) {
int minc = INF;
int p = -1;
for (int j = 0; j < n; j++)
if (!vis[j] && minc > lowc[j]) {
minc = lowc[j];
p = j;
}
if (minc == INF) return -1; //原图不连通
ans += minc;
vis[p] = true;
for (int j = 0; j < n; j++) {
if (!vis[j] && lowc[j] > cost[p][j]) lowc[j] = cost[p][j];
}
}
return ans;
}

SecondMST (Prim)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/*
* 次小生成树
* 求最小生成树时,用数组 Max[i][j] 来表示 MST 中 i 到 j 最大边权
* 求完后,直接枚举所有不在 MST 中的边,替换掉最大边权的边,更新答案
* 点的编号从 0 开始
*/
#include <string.h>
#include <algorithm>
#include <cmath>
using namespace std;

const int MAXN = 110;
const int INF = 0x3f3f3f3f;
bool vis[MAXN];
int lowc[MAXN];
int pre[MAXN];
int Max[MAXN][MAXN];
// Max[i][j] 表示在最小生成树中从 i 到 j 的路径中的最大边权
bool used[MAXN][MAXN];
int Prim(int cost[][MAXN], int n) {
int ans = 0;
memset(vis, false, sizeof(vis));
memset(Max, 0, sizeof(Max));
memset(used, false, sizeof(used));
vis[0] = true;
pre[0] = -1;
for (int i = 1; i < n; i++) {
lowc[i] = cost[0][i];
pre[i] = 0;
}
lowc[0] = 0;
for (int i = 1; i < n; i++) {
int minc = INF;
int p = -1;

for (int j = 0; j < n; j++)
if (!vis[j] && minc > lowc[j]) {
minc = lowc[j];
p = j;
}
if (minc == INF) return -1;
ans += minc;
vis[p] = true;
used[p][pre[p]] = used[pre[p]][p] = true;
for (int j = 0; j < n; j++) {
if (vis[j] && j != p)
Max[j][p] = Max[p][j] = max(Max[j][pre[p]], lowc[p]);
if (!vis[j] && lowc[j] > cost[p][j]) {
lowc[j] = cost[p][j];
pre[j] = p;
}
}
}
return ans;
}

int smst(int cost[][MAXN], int n, int ans) {
int Min = INF;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (cost[i][j] != INF && !used[i][j]) {
Min = min(Min, ans + cost[i][j] - Max[i][j]);
}
if (Min == INF) return -1; //不存在
return Min;
}

代码

POJ-1251 Jungle Roads

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
// POJ-1251 Jungle Roads
// https://vjudge.net/problem/POJ-1251

#include <string.h>
#include <algorithm>
#include <cstdio>
using namespace std;

const int MAXN = 110; //最大点数
const int MAXM = 10000; //最大边数
int F[MAXN]; //并查集使用
struct Edge {
int u, v, w;
} edge[MAXM]; //存储边的信息,包括起点/终点/权值
int tol; //边数,加边前赋值为 0
void addedge(int u, int v, int w) {
edge[tol].u = u;
edge[tol].v = v;
edge[tol++].w = w;
}
//排序函数,讲边按照权值从小到大排序
bool cmp(Edge a, Edge b) { return a.w < b.w; }
int find(int x) {
if (F[x] == -1)
return x;
else
return F[x] = find(F[x]);
}
//传入点数,返回最小生成树的权值,如果不连通返回 -1
int Kruskal(int n) {
memset(F, -1, sizeof(F));
sort(edge, edge + tol, cmp);
int cnt = 0; //计算加入的边数
int ans = 0;
for (int i = 0; i < tol; i++) {
int u = edge[i].u;
int v = edge[i].v;
int w = edge[i].w;
int t1 = find(u);
int t2 = find(v);
if (t1 != t2) {
ans += w;
F[t1] = t2;
cnt++;
}
if (cnt == n - 1) break;
}
if (cnt < n - 1)
return -1; //不连通
else
return ans;
}

int main() {
int n;
while (~scanf("%d", &n)) {
if (n == 0) break;
tol = 0;
for (int i = 0; i < n - 1; i++) {
char x;
int m;
scanf(" %c%d", &x, &m);
for (int j = 0; j < m; j++) {
char y;
int w;
scanf(" %c%d", &y, &w);
addedge(x - 'A', y - 'A', w);
}
}
int ans = Kruskal(n);
printf("%d\n", ans);
}
return 0;
}

// 裸题,scanf %c 读入尴尬
// scanf(" %c%d", &x, &m);

POJ-1287 Networking

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
// POJ-1287 Networking
// https://vjudge.net/problem/POJ-1287

#include <string.h>
#include <algorithm>
#include <cstdio>
using namespace std;

const int MAXN = 110; //最大点数
const int MAXM = 10000; //最大边数
int F[MAXN]; //并查集使用
struct Edge {
int u, v, w;
} edge[MAXM]; //存储边的信息,包括起点/终点/权值
int tol; //边数,加边前赋值为 0
void addedge(int u, int v, int w) {
edge[tol].u = u;
edge[tol].v = v;
edge[tol++].w = w;
}
//排序函数,讲边按照权值从小到大排序
bool cmp(Edge a, Edge b) { return a.w < b.w; }
int find(int x) {
if (F[x] == -1)
return x;
else
return F[x] = find(F[x]);
}
//传入点数,返回最小生成树的权值,如果不连通返回 -1
int Kruskal(int n) {
memset(F, -1, sizeof(F));
sort(edge, edge + tol, cmp);
int cnt = 0; //计算加入的边数
int ans = 0;
for (int i = 0; i < tol; i++) {
int u = edge[i].u;
int v = edge[i].v;
int w = edge[i].w;
int t1 = find(u);
int t2 = find(v);
if (t1 != t2) {
ans += w;
F[t1] = t2;
cnt++;
}
if (cnt == n - 1) break;
}
if (cnt < n - 1)
return -1; //不连通
else
return ans;
}

int main() {
int n, m;
while (~scanf("%d", &n)) {
if (n == 0) break;
tol = 0;
scanf("%d", &m);
for (int i = 0; i < m; i++) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
addedge(a, b, c);
}
int ans = Kruskal(n);
printf("%d\n", ans);
}
return 0;
}

// 裸题

POJ-2031 Building a Space Station

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
// POJ-2031 Building a Space Station
// https://vjudge.net/problem/POJ-2031

#include <string.h>
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;

const int MAXN = 110; //最大点数
const int MAXM = 10000; //最大边数
int F[MAXN]; //并查集使用
struct Edge {
int u, v;
double w;
} edge[MAXM]; //存储边的信息,包括起点/终点/权值
int tol; //边数,加边前赋值为 0
void addedge(int u, int v, double w) {
edge[tol].u = u;
edge[tol].v = v;
edge[tol++].w = w;
}
//排序函数,讲边按照权值从小到大排序
bool cmp(Edge a, Edge b) { return a.w < b.w; }
int find(int x) {
if (F[x] == -1)
return x;
else
return F[x] = find(F[x]);
}
//传入点数,返回最小生成树的权值,如果不连通返回 -1
double Kruskal(int n) {
memset(F, -1, sizeof(F));
sort(edge, edge + tol, cmp);
int cnt = 0; //计算加入的边数
double ans = 0;
for (int i = 0; i < tol; i++) {
int u = edge[i].u;
int v = edge[i].v;
double w = edge[i].w;
int t1 = find(u);
int t2 = find(v);
if (t1 != t2) {
ans += w;
F[t1] = t2;
cnt++;
}
if (cnt == n - 1) break;
}
if (cnt < n - 1)
return -1; //不连通
else
return ans;
}

double len(double x, double y, double z, double xx, double yy, double zz) {
return sqrt((xx - x) * (xx - x) + (yy - y) * (yy - y) + (zz - z) * (zz - z));
}
double cirlen(double x, double y, double z, double r, double xx, double yy,
double zz, double rr) {
double ll = len(x, y, z, xx, yy, zz);
if (ll - r - rr < 1e-5) {
return 0;
} else {
return ll - r - rr;
}
}
double xp[MAXN];
double yp[MAXN];
double zp[MAXN];
double rp[MAXN];

int main() {
int n;
while (~scanf("%d", &n)) {
if (n == 0) break;
tol = 0;
for (int i = 0; i < n; i++) {
scanf("%lf%lf%lf%lf", &xp[i], &yp[i], &zp[i], &rp[i]);
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
addedge(i, j,
cirlen(xp[i], yp[i], zp[i], rp[i], xp[j], yp[j], zp[j], rp[j]));
}
}
double ans = Kruskal(n);
printf("%.3f\n", ans);
}
return 0;
}

// 浮点数的最小生成树,球之间的距离,距离小于零,就建一条权为 0 的边
// POJ尴尬精度 %f

POJ-2421 Constructing Roads

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
// POJ-2421 Constructing Roads
// https://vjudge.net/problem/POJ-2421

#include <string.h>
#include <algorithm>
#include <cstdio>
using namespace std;

const int MAXN = 110; //最大点数
const int MAXM = 10000; //最大边数
int F[MAXN]; //并查集使用
struct Edge {
int u, v, w;
} edge[MAXM]; //存储边的信息,包括起点/终点/权值
int tol; //边数,加边前赋值为 0
void addedge(int u, int v, int w) {
edge[tol].u = u;
edge[tol].v = v;
edge[tol++].w = w;
} //排序函数,讲边按照权值从小到大排序
bool cmp(Edge a, Edge b) { return a.w < b.w; }
int find(int x) {
if (F[x] == -1)
return x;
else
return F[x] = find(F[x]);
} //传入点数,返回最小生成树的权值,如果不连通返回 -1
int Kruskal(int n) {
memset(F, -1, sizeof(F));
sort(edge, edge + tol, cmp);
int cnt = 0; //计算加入的边数

int ans = 0;
for (int i = 0; i < tol; i++) {
int u = edge[i].u;
int v = edge[i].v;
int w = edge[i].w;
int t1 = find(u);
int t2 = find(v);
if (t1 != t2) {
ans += w;
F[t1] = t2;
cnt++;
}
if (cnt == n - 1) break;
}
if (cnt < n - 1)
return -1; //不连通
else
return ans;
}

int mapx[MAXN][MAXN];

int main() {
int N;
scanf("%d", &N);
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
scanf("%d", &mapx[i][j]);
}
}

int Q;
scanf("%d", &Q);
for (int i = 0; i < Q; i++) {
int a, b;
scanf("%d%d", &a, &b);
mapx[a][b] = 0;
mapx[b][a] = 0;
}
for (int i = 1; i <= N; i++) {
for (int j = i + 1; j <= N; j++) {
if (i == j) continue;
addedge(i, j, min(mapx[i][j], mapx[j][i]));
}
}
int ans = Kruskal(N);
printf("%d\n", ans);
}

// 有一些路已建好,把边权改为 0 就好了

ZOJ-1586 QS Network

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
// ZOJ-1586 QS Network
// https://vjudge.net/problem/ZOJ-1586

#include <string.h>
#include <algorithm>
#include <cstdio>
using namespace std;

const int MAXN = 1100; //最大点数
const int MAXM = 2000000; //最大边数
int F[MAXN]; //并查集使用

int codec[MAXN]; // *&*

struct Edge {
int u, v, w;
} edge[MAXM]; //存储边的信息,包括起点/终点/权值
int tol; //边数,加边前赋值为 0
void addedge(int u, int v, int w) {
edge[tol].u = u;
edge[tol].v = v;
edge[tol++].w = w;
}
//排序函数,讲边按照权值从小到大排序
bool cmp(Edge a, Edge b) { return a.w < b.w; }
int find(int x) {
if (F[x] == -1)
return x;
else
return F[x] = find(F[x]);
}
//传入点数,返回最小生成树的权值,如果不连通返回 -1
int Kruskal(int n) {
memset(F, -1, sizeof(F));
sort(edge, edge + tol, cmp);
int cnt = 0; //计算加入的边数
int ans = 0;
for (int i = 0; i < tol; i++) {
int u = edge[i].u;
int v = edge[i].v;
int w = edge[i].w;
int t1 = find(u);
int t2 = find(v);
if (t1 != t2) {
ans += w;

F[t1] = t2;
cnt++;
}
if (cnt == n - 1) break;
}
if (cnt < n - 1)
return -1; //不连通
else
return ans;
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
tol = 0;
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &codec[i]);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int w;
scanf("%d", &w);
if (i < j) addedge(i, j, w + codec[i] + codec[j]);
}
}
int ans = Kruskal(n);
printf("%d\n", ans);
}
return 0;
}

// 加边时,加一下适配器的价格

HDU-1233 还是畅通工程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
// HDU-1233 还是畅通工程
// https://vjudge.net/problem/HDU-1233

#include <string.h>
#include <algorithm>
#include <cstdio>
using namespace std;
const int MAXN = 110; //最大点数
const int MAXM = 10000; //最大边数
int F[MAXN]; //并查集使用
struct Edge {
int u, v, w;
} edge[MAXM]; //存储边的信息,包括起点/终点/权值
int tol; //边数,加边前赋值为 0
void addedge(int u, int v, int w) {
edge[tol].u = u;
edge[tol].v = v;
edge[tol++].w = w;
} //排序函数,讲边按照权值从小到大排序
bool cmp(Edge a, Edge b) { return a.w < b.w; }
int find(int x) {
if (F[x] == -1)
return x;
else
return F[x] = find(F[x]);
} //传入点数,返回最小生成树的权值,如果不连通返回 -1
int Kruskal(int n) {
memset(F, -1, sizeof(F));
sort(edge, edge + tol, cmp);
int cnt = 0; //计算加入的边数

int ans = 0;
for (int i = 0; i < tol; i++) {
int u = edge[i].u;
int v = edge[i].v;
int w = edge[i].w;
int t1 = find(u);
int t2 = find(v);
if (t1 != t2) {
ans += w;
F[t1] = t2;
cnt++;
}
if (cnt == n - 1) break;
}
if (cnt < n - 1)
return -1; //不连通
else
return ans;
}
int main() {
int n;
while (~scanf("%d", &n)) {
if (n == 0) break;
tol = 0;
int m = n * (n - 1) / 2;
for (int i = 0; i < m; i++) {
int a, b, w;
scanf("%d%d%d", &a, &b, &w);
addedge(a, b, w);
}
int ans = Kruskal(n);
printf("%d\n", ans);
}
return 0;
}

// 裸题

HDU-1875 畅通工程再续

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
// HDU-1875 畅通工程再续
// https://vjudge.net/problem/HDU-1875

#include <string.h>
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;

const int MAXN = 310; //最大点数
const int MAXM = 10000; //最大边数
int F[MAXN]; //并查集使用
struct Edge {
int u, v;
double w;
} edge[MAXM]; //存储边的信息,包括起点/终点/权值
int tol; //边数,加边前赋值为 0
void addedge(int u, int v, double w) {
edge[tol].u = u;
edge[tol].v = v;
edge[tol++].w = w;
}
//排序函数,讲边按照权值从小到大排序
bool cmp(Edge a, Edge b) { return a.w < b.w; }
int find(int x) {
if (F[x] == -1)
return x;
else
return F[x] = find(F[x]);
}
//传入点数,返回最小生成树的权值,如果不连通返回 -1
double Kruskal(int n) {
memset(F, -1, sizeof(F));
sort(edge, edge + tol, cmp);
int cnt = 0; //计算加入的边数
double ans = 0;
for (int i = 0; i < tol; i++) {
int u = edge[i].u;
int v = edge[i].v;
double w = edge[i].w;
int t1 = find(u);
int t2 = find(v);
if (t1 != t2) {
ans += w;
F[t1] = t2;
cnt++;
}
if (cnt == n - 1) break;
}
if (cnt < n - 1)
return -1; //不连通
else
return ans;
}

double len(double x, double y, double xx, double yy) {
return sqrt((xx - x) * (xx - x) + (yy - y) * (yy - y));
}

double xp[MAXN];
double yp[MAXN];

int main() {
int T;
scanf("%d", &T);
while (T--) {
int n;
scanf("%d", &n);
if (n == 0) break;
tol = 0;
for (int i = 1; i <= n; i++) {
scanf("%lf%lf", &xp[i], &yp[i]);
}
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
double xly = len(xp[i], yp[i], xp[j], yp[j]);
if (xly >= 10 && xly <= 1000) addedge(i, j, xly * 100);
}
}
double ans = Kruskal(n);
if (ans > 0) {
printf("%.1f\n", ans);

} else {
printf("oh!\n");
}
}
return 0;
}

// 浮点数,条件连边

HDU-1301 Jungle Roads

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
// HDU-1301 Jungle Roads
// https://vjudge.net/problem/HDU-1301

#include <string.h>
#include <algorithm>
#include <cstdio>
using namespace std;

const int MAXN = 110; //最大点数
const int MAXM = 10000; //最大边数
int F[MAXN]; //并查集使用
struct Edge {
int u, v, w;
} edge[MAXM]; //存储边的信息,包括起点/终点/权值
int tol; //边数,加边前赋值为 0
void addedge(int u, int v, int w) {
edge[tol].u = u;
edge[tol].v = v;
edge[tol++].w = w;
}
//排序函数,讲边按照权值从小到大排序
bool cmp(Edge a, Edge b) { return a.w < b.w; }
int find(int x) {
if (F[x] == -1)
return x;
else
return F[x] = find(F[x]);
}
//传入点数,返回最小生成树的权值,如果不连通返回 -1
int Kruskal(int n) {
memset(F, -1, sizeof(F));
sort(edge, edge + tol, cmp);
int cnt = 0; //计算加入的边数
int ans = 0;
for (int i = 0; i < tol; i++) {
int u = edge[i].u;
int v = edge[i].v;
int w = edge[i].w;
int t1 = find(u);
int t2 = find(v);
if (t1 != t2) {
ans += w;
F[t1] = t2;
cnt++;
}
if (cnt == n - 1) break;
}
if (cnt < n - 1)
return -1; //不连通
else
return ans;
}

int main() {
int n;
while (~scanf("%d", &n)) {
if (n == 0) break;
tol = 0;
for (int i = 0; i < n - 1; i++) {
char x;
int m;
scanf(" %c%d", &x, &m);
for (int j = 0; j < m; j++) {
char y;
int w;
scanf(" %c%d", &y, &w);
addedge(x - 'A', y - 'A', w);
}
}
int ans = Kruskal(n);
printf("%d\n", ans);
}
return 0;
}

// 竟然有重复的题,一模一样 -> POJ-1251
// 裸题,scanf %c 读入尴尬
// scanf(" %c%d", &x, &m);

POJ-2349 Arctic Network

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
// POJ-2349 Arctic Network
// https://vjudge.net/problem/POJ-2349

#include <string.h>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <vector>
using namespace std;

const int MAXN = 510; //最大点数
const int MAXM = 250000; //最大边数
int F[MAXN]; //并查集使用
vector<double> vd;
struct Edge {
int u, v;
double w;
} edge[MAXM]; //存储边的信息,包括起点/终点/权值
int tol; //边数,加边前赋值为 0
void addedge(int u, int v, double w) {
edge[tol].u = u;
edge[tol].v = v;
edge[tol++].w = w;
}
//排序函数,讲边按照权值从小到大排序
bool cmp(Edge a, Edge b) { return a.w < b.w; }

int find(int x) {
if (F[x] == -1)
return x;
else
return F[x] = find(F[x]);
}
//传入点数,返回最小生成树的权值,如果不连通返回 -1
double Kruskal(int n) {
memset(F, -1, sizeof(F));
sort(edge, edge + tol, cmp);
int cnt = 0; //计算加入的边数
double ans = 0;
for (int i = 0; i < tol; i++) {
int u = edge[i].u;
int v = edge[i].v;
double w = edge[i].w;
int t1 = find(u);
int t2 = find(v);
if (t1 != t2) {
ans = max(ans, w);
vd.push_back(w);
// ans += w;
F[t1] = t2;
cnt++;
}
if (cnt == n - 1) break;
}
if (cnt < n - 1)
return -1; //不连通
else
return ans;
}

double len(double x, double y, double xx, double yy) {
return sqrt((xx - x) * (xx - x) + (yy - y) * (yy - y));
}

double xp[MAXN];
double yp[MAXN];

int main() {
int T;
scanf("%d", &T);
while (T--) {
vd.clear();
int n, s;
scanf("%d%d", &s, &n);
if (n == 0) break;
tol = 0;
for (int i = 1; i <= n; i++) {
scanf("%lf%lf", &xp[i], &yp[i]);
}
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
double xly = len(xp[i], yp[i], xp[j], yp[j]);
addedge(i, j, xly);
}
}
double ans = Kruskal(n);
ans = vd[vd.size() - s];
printf("%.2f\n", ans);
}
return 0;
}

// 最小生成树的第 K 大边

POJ-1751 Highways

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
// POJ-1751 Highways
// https://vjudge.net/problem/POJ-1751

#include <string.h>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <vector>
using namespace std;

const int MAXN = 1000; //最大点数
const int MAXM = 1000000; //最大边数
vector<int> vx;
vector<int> vy;

int F[MAXN]; //并查集使用
struct Edge {
int u, v;
double w;
} edge[MAXM]; //存储边的信息,包括起点/终点/权值
int tol; //边数,加边前赋值为 0
void addedge(int u, int v, double w) {
edge[tol].u = u;
edge[tol].v = v;
edge[tol++].w = w;
}
//排序函数,讲边按照权值从小到大排序
bool cmp(Edge a, Edge b) { return a.w < b.w; }
int find(int x) {
if (F[x] == -1)
return x;
else
return F[x] = find(F[x]);
}
//传入点数,返回最小生成树的权值,如果不连通返回 -1
double Kruskal(int n) {
memset(F, -1, sizeof(F));
sort(edge, edge + tol, cmp);
int cnt = 0; //计算加入的边数
double ans = 0;
for (int i = 0; i < tol; i++) {
int u = edge[i].u;
int v = edge[i].v;
double w = edge[i].w;
int t1 = find(u);
int t2 = find(v);
if (t1 != t2) {
ans += w;
if (w > 1e-5) {
vx.push_back(u);
vy.push_back(v);
}

F[t1] = t2;
cnt++;
}
if (cnt == n - 1) break;
}
if (cnt < n - 1)
return -1; //不连通
else
return ans;
}

double len(double x, double y, double xx, double yy) {
return sqrt((xx - x) * (xx - x) + (yy - y) * (yy - y));
}

double xp[MAXN];
double yp[MAXN];

int main() {
int n;
scanf("%d", &n);
tol = 0;
for (int i = 1; i <= n; i++) {
scanf("%lf%lf", &xp[i], &yp[i]);
}
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
double xly = len(xp[i], yp[i], xp[j], yp[j]);
addedge(i, j, xly * 100);
}
}
int q;
scanf("%d", &q);
for (int i = 0; i < q; i++) {
int a, b;
scanf("%d%d", &a, &b);
addedge(a, b, 0);
}
double ans = Kruskal(n);

for (int i = 0; i < vx.size(); i++) {
printf("%d %d\n", vx[i], vy[i]);
}

return 0;
}

// 求最小生成树的边,加 0 权边

UVA-10147 Highways

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
// UVA-10147 Highways
// https://vjudge.net/problem/UVA-10147

#include <string.h>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <vector>
using namespace std;

const int MAXN = 1000; //最大点数
const int MAXM = 1000000; //最大边数
vector<int> vx;
vector<int> vy;

int F[MAXN]; //并查集使用
struct Edge {
int u, v;
double w;
} edge[MAXM]; //存储边的信息,包括起点/终点/权值
int tol; //边数,加边前赋值为 0
void addedge(int u, int v, double w) {
edge[tol].u = u;
edge[tol].v = v;
edge[tol++].w = w;
}
//排序函数,讲边按照权值从小到大排序
bool cmp(Edge a, Edge b) { return a.w < b.w; }
int find(int x) {
if (F[x] == -1)
return x;
else
return F[x] = find(F[x]);
}
//传入点数,返回最小生成树的权值,如果不连通返回 -1
double Kruskal(int n) {
memset(F, -1, sizeof(F));
sort(edge, edge + tol, cmp);
int cnt = 0; //计算加入的边数
double ans = 0;
for (int i = 0; i < tol; i++) {
int u = edge[i].u;
int v = edge[i].v;
double w = edge[i].w;
int t1 = find(u);
int t2 = find(v);
if (t1 != t2) {
ans += w;
if (w > 0) {
vx.push_back(u);
vy.push_back(v);
}

F[t1] = t2;
cnt++;
}
if (cnt == n - 1) break;
}
if (cnt < n - 1)
return -1; //不连通
else
return ans;
}

double len(double x, double y, double xx, double yy) {
return sqrt((xx - x) * (xx - x) + (yy - y) * (yy - y));
}

double xp[MAXN];
double yp[MAXN];

int main() {
int T;
scanf("%d", &T);
while (T--) {
vx.clear();
vy.clear();

int n;
scanf("%d", &n);
tol = 0;
for (int i = 1; i <= n; i++) {
scanf("%lf%lf", &xp[i], &yp[i]);
}
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
double xly = len(xp[i], yp[i], xp[j], yp[j]);
addedge(i, j, xly * 100);
}
}
int q;
scanf("%d", &q);
for (int i = 0; i < q; i++) {
int a, b;
scanf("%d%d", &a, &b);
addedge(a, b, 0);
}
double ans = Kruskal(n);

for (int i = 0; i < vx.size(); i++) {
printf("%d %d\n", vx[i], vy[i]);
}
if (vx.size() == 0) printf("No new highways need\n");
if (T != 0) printf("\n");
}

return 0;
}

// 求最小生成树的边,加 0 权边

POJ-1258 Agri-Net

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
// POJ-1258 Agri-Net
// https://vjudge.net/problem/POJ-1258

#include <string.h>
#include <algorithm>
#include <cstdio>
using namespace std;

const int MAXN = 110; //最大点数
const int MAXM = 10000; //最大边数
int F[MAXN]; //并查集使用
struct Edge {
int u, v, w;
} edge[MAXM]; //存储边的信息,包括起点/终点/权值
int tol; //边数,加边前赋值为 0
void addedge(int u, int v, int w) {
edge[tol].u = u;
edge[tol].v = v;
edge[tol++].w = w;
} //排序函数,讲边按照权值从小到大排序
bool cmp(Edge a, Edge b) { return a.w < b.w; }
int find(int x) {
if (F[x] == -1)
return x;
else
return F[x] = find(F[x]);
} //传入点数,返回最小生成树的权值,如果不连通返回 -1
int Kruskal(int n) {
memset(F, -1, sizeof(F));
sort(edge, edge + tol, cmp);
int cnt = 0; //计算加入的边数

int ans = 0;
for (int i = 0; i < tol; i++) {
int u = edge[i].u;
int v = edge[i].v;
int w = edge[i].w;
int t1 = find(u);
int t2 = find(v);
if (t1 != t2) {
ans += w;
F[t1] = t2;
cnt++;
}
if (cnt == n - 1) break;
}
if (cnt < n - 1)
return -1; //不连通
else
return ans;
}

int main() {
int n;
while (~scanf("%d", &n)) {
tol = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int w;
scanf("%d", &w);
addedge(i, j, w);
}
}
int ans = Kruskal(n);
printf("%d\n", ans);
}
return 0;
}

// 裸题

POJ-3026 Borg Maze

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
// POJ-3026 Borg Maze
// https://vjudge.net/problem/POJ-3026

#include <string.h>
#include <algorithm>
#include <cstdio>
#include <queue>
using namespace std;

const int MAXN = 1100; //最大点数
const int MAXM = 1000000; //最大边数
int F[MAXN]; //并查集使用
struct Edge {
int u, v, w;
} edge[MAXM]; //存储边的信息,包括起点/终点/权值
int tol; //边数,加边前赋值为 0
void addedge(int u, int v, int w) {
edge[tol].u = u;
edge[tol].v = v;
edge[tol++].w = w;
} //排序函数,讲边按照权值从小到大排序
bool cmp(Edge a, Edge b) { return a.w < b.w; }
int find(int x) {
if (F[x] == -1)
return x;
else
return F[x] = find(F[x]);
} //传入点数,返回最小生成树的权值,如果不连通返回 -1
int Kruskal(int n) {
memset(F, -1, sizeof(F));
sort(edge, edge + tol, cmp);
int cnt = 0; //计算加入的边数

int ans = 0;
for (int i = 0; i < tol; i++) {
int u = edge[i].u;
int v = edge[i].v;
int w = edge[i].w;
int t1 = find(u);
int t2 = find(v);
if (t1 != t2) {
ans += w;
F[t1] = t2;
cnt++;
}
if (cnt == n - 1) break;
}
if (cnt < n - 1)
return -1; //不连通
else
return ans;
}

int mapx[MAXN][MAXN];

int dirx[10] = {0, 1, 0, -1};
int diry[10] = {1, 0, -1, 0};

int n, m;
void bfs(int x, int y) {
bool vis[MAXN][MAXN];
memset(vis, false, sizeof(vis));
queue<pair<pair<int, int>, int> > Q;
Q.push(make_pair(make_pair(x, y), 0));
vis[x][y] = true;
while (!Q.empty()) {
int xt = Q.front().first.first;
int yt = Q.front().first.second;
int times = Q.front().second;
Q.pop();
if (mapx[x][y] != mapx[xt][yt] && mapx[xt][yt] != 0) {
addedge(mapx[x][y], mapx[xt][yt], times);
}
for (int i = 0; i < 4; i++) {
int tx = xt + dirx[i];
int ty = yt + diry[i];

if (tx >= 0 && ty >= 0 && tx < n && ty < m && !vis[tx][ty]) {
if (mapx[tx][ty] != -1) {
Q.push(make_pair(make_pair(tx, ty), times + 1));
vis[tx][ty] = true;
}
}
}
}
}

int main() {
int T;
scanf("%d", &T);
char str[100];
while (T--) {
tol = 0;
memset(mapx, -1, sizeof(mapx));
int cnt = 0;
scanf("%d%d", &n, &m);
gets(str);
for (int i = 0; i < m; i++) {
gets(str);
for (int j = 0; j < n; j++) {
if (str[j] == 'A' || str[j] == 'S') {
mapx[i][j] = ++cnt;
} else if (str[j] == ' ') {
mapx[i][j] = 0;
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (mapx[i][j] > 0) {
bfs(i, j);
}
}
}
int ans = Kruskal(cnt);
printf("%d\n", ans);
}
return 0;
}

// BFS + Kruskal
// 用无权图最短路权值加边
// 一开始 MAXN 和 MAXM 开小了,wa...wa...wa...

POJ-1789 Truck History

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
// POJ-1789 Truck History
// https://vjudge.net/problem/POJ-1789

#include <string.h>
#include <algorithm>
#include <cstdio>
using namespace std;

const int MAXN = 2010; //最大点数
const int INF = 0x3f3f3f3f;
bool vis[MAXN];
int lowc[MAXN];
int cost[MAXN][MAXN];
//点是 0 n-1
int Prim(int cost[][MAXN], int n) {
int ans = 0;
memset(vis, false, sizeof(vis));
vis[0] = true;
for (int i = 1; i < n; i++) lowc[i] = cost[0][i];
for (int i = 1; i < n; i++) {
int minc = INF;
int p = -1;
for (int j = 0; j < n; j++)
if (!vis[j] && minc > lowc[j]) {
minc = lowc[j];
p = j;
}
if (minc == INF) return -1; //原图不连通
ans += minc;
vis[p] = true;
for (int j = 0; j < n; j++) {
if (!vis[j] && lowc[j] > cost[p][j]) lowc[j] = cost[p][j];
}
}
return ans;
}
char str[MAXN][10];
int len(int a, int b) {
int ans = 0;
for (int i = 0; i < 7; i++) {
if (str[a][i] != str[b][i]) {
ans++;
}
}
return ans;
}

int main() {
int n;
while (~scanf("%d", &n)) {
if (n == 0) break;
for (int i = 0; i < n; i++) {
scanf("%s", str[i]);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) continue;
cost[i][j] = len(i, j);
}
}
int ans = Prim(cost, n);
printf("The highest possible quality is 1/%d.\n", ans);
}
return 0;
}

// Kruskal 超时,用 Prim !

POJ-1679 The Unique MST

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
// POJ-1679 The Unique MST
// https://vjudge.net/problem/POJ-1679

#include <string.h>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;

const int MAXN = 110;
const int INF = 0x3f3f3f3f;
bool vis[MAXN];
int lowc[MAXN];
int pre[MAXN];
int Max[MAXN][MAXN];
// Max[i][j] 表示在最小生成树中从 i 到 j 的路径中的最大边权
bool used[MAXN][MAXN];
int Prim(int cost[][MAXN], int n) {
int ans = 0;
memset(vis, false, sizeof(vis));
memset(Max, 0, sizeof(Max));
memset(used, false, sizeof(used));
vis[0] = true;
pre[0] = -1;
for (int i = 1; i < n; i++) {
lowc[i] = cost[0][i];
pre[i] = 0;
}
lowc[0] = 0;
for (int i = 1; i < n; i++) {
int minc = INF;
int p = -1;

for (int j = 0; j < n; j++)
if (!vis[j] && minc > lowc[j]) {
minc = lowc[j];
p = j;
}
if (minc == INF) return -1;
ans += minc;
vis[p] = true;
used[p][pre[p]] = used[pre[p]][p] = true;
for (int j = 0; j < n; j++) {
if (vis[j] && j != p)
Max[j][p] = Max[p][j] = max(Max[j][pre[p]], lowc[p]);
if (!vis[j] && lowc[j] > cost[p][j]) {
lowc[j] = cost[p][j];
pre[j] = p;
}
}
}
return ans;
}

int smst(int cost[][MAXN],int n,int ans)
{
int Min=INF;
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
if(cost[i][j]!=INF && !used[i][j])
{
Min=min(Min,ans+cost[i][j]-Max[i][j]);
}
if(Min==INF)return -1;//不存在
return Min;
}

int costx[MAXN][MAXN];

int main() {
int T;
scanf("%d", &T);
while (T--) {
memset(costx, 0x3f, sizeof(costx));
int n, m;
scanf("%d%d", &n, &m);
int sum = 0;
for (int i = 0; i < n; i++) costx[i][i] = 0;
for (int i = 0; i < m; i++) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
a--;
b--;
costx[a][b] = c;
costx[b][a] = c;
}
int ans = Prim(costx, n);
int ansMST = smst(costx, n,ans);

if (ans == ansMST) {
printf("Not Unique!\n");
} else {
printf("%d\n", ans);
}
}
return 0;
}

// 次小生成树,不知道为什么最小生成树计数不行
// kuangbin 题解:https://www.cnblogs.com/kuangbin/p/3147329.html
Donate comment here