kuangbin 专题六 最小生成树

Posted on Edited on In

题目详单见 [kuangbin带你飞]专题1-23。
算法介绍见 最小生成树 - OI Wiki。

POJ-1251/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
#include <iostream>
#include <algorithm>
#define N 26
using namespace std;
int n, m, p[N];
char c;
struct edge
{
    int w, u, v;
    bool operator<(const edge &a) const { return w < a.w; }
} e[N * N];
int find(int x)
{
    return p[x] == x ? x : p[x] = find(p[x]);
}
int kruskal()
{
    int res = 0;
    for (int i = 0; i < n; ++i)
        p[i] = i;
    sort(e, e + m);
    for (int i = 0; i < m; ++i)
    {
        int a = find(e[i].u), b = find(e[i].v);
        if (a != b)
            p[a] = b, res += e[i].w;
    }
    return res;
}
int main()
{
    while (cin >> n, n)
    {
        m = 0;
        for (int i = 1, u, k, w; i < n; ++i)
        {
            cin >> c >> k;
            u = c - 'A';
            while (k--)
            {
                cin >> c >> w;
                e[m++] = {w, u, c - 'A'};
            }
        }
        cout << kruskal() << endl;
    }
    return 0;
}
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
#include <iostream>
#include <cstring>
#include <algorithm>
#define N 26
using namespace std;
int n, g[N][N], d[N];
bool st[N];
char c;
int prim()
{
    int res = 0;
    for (int i = 0; i < n; ++i)
        d[i] = 0x3f3f3f3f, st[i] = 0;
    d[0] = 0;
    for (int i = 0; i < n; ++i)
    {
        int t = -1;
        for (int j = 0; j < n; ++j)
            if (!st[j] && (t == -1 || d[j] < d[t]))
                t = j;
        st[t] = 1;
        if (i)
            res += d[t];
        for (int j = 0; j < n; ++j)
            if (!st[j] && d[j] > g[t][j])
                d[j] = g[t][j];
    }
    return res;
}
int main()
{
    while (cin >> n, n)
    {
        memset(g, 0x3f, sizeof g);
        for (int i = 1, u, k, w; i < n; ++i)
        {
            cin >> c >> k;
            u = c - 'A';
            while (k--)
            {
                cin >> c >> w;
                g[u][c - 'A'] = g[c - 'A'][u] = w;
            }
        }
        cout << prim() << endl;
    }
    return 0;
}

POJ-1287 Networking

最小生成树模板题+1，输入更简单。

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
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 51, M = 1500;
int n, m, p[N];
struct edge
{
    int w, u, v;
    bool operator<(const edge &a) const { return w < a.w; }
} e[M];
int find(int x)
{
    return p[x] == x ? x : p[x] = find(p[x]);
}
int kruskal()
{
    int res = 0;
    for (int i = 1; i <= n; ++i)
        p[i] = i;
    sort(e, e + m);
    for (int i = 0; i < m; ++i)
    {
        int a = find(e[i].u), b = find(e[i].v);
        if (a != b)
            p[a] = b, res += e[i].w;
    }
    return res;
}
int main()
{
    while (scanf("%d", &n), n)
    {
        scanf("%d", &m);
        for (int i = 0, a, b, c; i < m; ++i)
        {
            scanf("%d%d%d", &a, &b, &c);
            e[i] = {c, a, b};
        }
        printf("%d\n", kruskal());
    }
    return 0;
}
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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 51;
int n, m, g[N][N], d[N];
bool st[N];
int prim()
{
    int res = 0;
    memset(d, 0x3f, sizeof d);
    memset(st, 0, sizeof st);
    d[0] = 0;
    for (int i = 0; i < n; ++i)
    {
        int t = -1;
        for (int j = 1; j <= n; ++j)
            if (!st[j] && (t == -1 || d[j] < d[t]))
                t = j;
        st[t] = 1;
        if (i)
            res += d[t];
        for (int j = 1; j <= n; ++j)
            if (!st[j] && d[j] > g[t][j])
                d[j] = g[t][j];
    }
    return res;
}
int main()
{
    while (scanf("%d", &n), n)
    {
        scanf("%d", &m);
        memset(g, 0x3f, sizeof g);
        for (int i = 0, a, b, c; i < m; ++i)
        {
            scanf("%d%d%d", &a, &b, &c);
            g[a][b] = g[b][a] = min(g[a][b], c);
        }
        printf("%d\n", prim());
    }
    return 0;
}

POJ-2031 Building a Space Station

最小生成树模板题+2，计算各个球体的距离，注意 double 类型的初始化、输入和输出。

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
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 100;
int n, m, p[N];
double x[N], y[N], z[N], r[N];
double get_dist(int i, int j)
{
    double d1 = sqrt(pow(x[i] - x[j], 2) + pow(y[i] - y[j], 2) + pow(z[i] - z[j], 2));
    double d2 = r[i] + r[j];
    return d2 >= d1 ? 1e-9 : d1 - d2;
}
struct edge
{
    double w;
    int u, v;
    bool operator<(const edge &a) const { return w < a.w; }
} e[N * N];
int find(int x)
{
    return p[x] == x ? x : p[x] = find(p[x]);
}
double kruskal()
{
    double res = 0;
    for (int i = 0; i < n; ++i)
        p[i] = i;
    sort(e, e + m);
    for (int i = 0; i < m; ++i)
    {
        int a = find(e[i].u), b = find(e[i].v);
        if (a != b)
            p[a] = b, res += e[i].w;
    }
    return res;
}
int main()
{
    while (scanf("%d", &n), n)
    {
        m = 0;
        for (int i = 0; i < n; ++i)
            scanf("%lf%lf%lf%lf", x + i, y + i, z + i, r + i);
        for (int i = 0; i < n; ++i)
            for (int j = i + 1; j < n; ++j)
                e[m++] = {get_dist(i, j), i, j};
        printf("%.3lf\n", kruskal());
    }

    return 0;
}
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
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 100;
int n;
double x[N], y[N], z[N], r[N], g[N][N], d[N];
bool st[N];
double get_dist(int i, int j)
{
    double d1 = sqrt(pow(x[i] - x[j], 2) + pow(y[i] - y[j], 2) + pow(z[i] - z[j], 2));
    double d2 = r[i] + r[j];
    return d2 >= d1 ? 1e-9 : d1 - d2;
}
double prim()
{
    double res = 0;
    for (int i = 0; i < n; ++i)
        d[i] = 1e19, st[i] = 0;
    d[0] = 0;
    for (int i = 0; i < n; ++i)
    {
        int t = -1;
        for (int j = 0; j < n; ++j)
            if (!st[j] && (t == -1 || d[j] < d[t]))
                t = j;
        st[t] = 1;
        if (i)
            res += d[t];
        for (int j = 0; j < n; ++j)
            if (!st[j] && d[j] > g[t][j])
                d[j] = g[t][j];
    }
    return res;
}
int main()
{
    while (scanf("%d", &n), n)
    {
        for (int i = 0; i < n; ++i)
            scanf("%lf%lf%lf%lf", x + i, y + i, z + i, r + i);
        for (int i = 0; i < n; ++i)
            for (int j = i + 1; j < n; ++j)
                g[i][j] = g[j][i] = get_dist(i, j);
        printf("%.3lf\n", prim());
    }

    return 0;
}

POJ-2421 Constructing Roads

最小生成树模板题+3。

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
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100;
int n, m, q, a, b, g[N][N], p[N];
struct edge
{
    int w, u, v;
    bool operator<(const edge &a) const { return w < a.w; }
} e[N * N];
int find(int x)
{
    return p[x] == x ? x : p[x] = find(p[x]);
}
int kruskal()
{
    int res = 0;
    for (int i = 0; i < n; ++i)
        p[i] = i;
    sort(e, e + m);
    for (int i = 0; i < m; ++i)
    {
        int a = find(e[i].u), b = find(e[i].v);
        if (a != b)
            p[a] = b, res += e[i].w;
    }
    return res;
}
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            scanf("%d", &g[i][j]);
    scanf("%d", &q);
    while (q--)
    {
        scanf("%d%d", &a, &b);
        --a, --b;
        g[a][b] = g[b][a] = 0;
    }
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
            e[m++] = {g[i][j], i, j};
    printf("%d\n", kruskal());
    return 0;
}
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
#include <cstdio>
using namespace std;
const int N = 100;
int n, q, a, b, g[N][N], d[N];
bool st[N];
int prim()
{
    int res = 0;
    for (int i = 0; i < n; ++i)
        d[i] = 0x3f3f3f3f, st[i] = 0;
    d[0] = 0;
    for (int i = 0; i < n; ++i)
    {
        int t = -1;
        for (int j = 0; j < n; ++j)
            if (!st[j] && (t == -1 || d[j] < d[t]))
                t = j;
        st[t] = 1;
        if (i)
            res += d[t];
        for (int j = 0; j < n; ++j)
            if (!st[j] && d[j] > g[t][j])
                d[j] = g[t][j];
    }
    return res;
}
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            scanf("%d", &g[i][j]);
    scanf("%d", &q);
    while (q--)
    {
        scanf("%d%d", &a, &b);
        --a, --b;
        g[a][b] = g[b][a] = 0;
    }
    printf("%d\n", prim());
    return 0;
}

ZOJ-1586 QS Network

最小生成树模板题+4，只不过点与点的距离有点特殊。

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 500
using namespace std;
int t, n, m, price[N], g[N][N], p[N];
struct edge
{
    int w, u, v;
    bool operator<(const edge &a) const { return w < a.w; }
} e[N * N];
int find(int x)
{
    return p[x] == x ? x : p[x] = find(p[x]);
}
int kruskal()
{
    int res = 0;
    for (int i = 0; i < n; ++i)
        p[i] = i;
    sort(e, e + m);
    for (int i = 0; i < m; ++i)
    {
        int a = find(e[i].u), b = find(e[i].v);
        if (a != b)
            p[a] = b, res += e[i].w;
    }
    return res;
}
int main()
{
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &n);
        for (int i = 0; i < n; ++i)
            scanf("%d", price + i);
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                scanf("%d", &g[i][j]);
        m = 0;
        for (int i = 0; i < n; ++i)
            for (int j = i + 1; j < n; ++j)
                e[m++] = {g[i][j] + price[i] + price[j], i, j};
        printf("%d\n", kruskal());
    }
    return 0;
}
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
#include <cstdio>
#include <cstring>
#define N 500
using namespace std;
int t, n, price[N], g[N][N], d[N];
bool st[N];
int prim()
{
    int res = 0;
    memset(d, 0x3f, sizeof d);
    memset(st, 0, sizeof st);
    d[0] = 0;
    for (int i = 0; i < n; ++i)
    {
        int t = -1;
        for (int j = 0; j < n; ++j)
            if (!st[j] && (t == -1 || d[j] < d[t]))
                t = j;
        st[t] = 1;
        if (i)
            res += d[t];
        for (int j = 0; j < n; ++j)
            if (!st[j] && d[j] > g[t][j])
                d[j] = g[t][j];
    }
    return res;
}
int main()
{
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &n);
        for (int i = 0; i < n; ++i)
            scanf("%d", price + i);
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                scanf("%d", &g[i][j]);
        for (int i = 0; i < n; ++i)
            for (int j = i + 1; j < n; ++j)
                g[i][j] = g[j][i] = g[i][j] + price[i] + price[j];
        printf("%d\n", prim());
    }
    return 0;
}

POJ-1789 Truck History

最小生成树模板题+5，只不过是点与点之间的距离有点特殊。

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
#include <cstdio>
#include <algorithm>
#define N 2000
using namespace std;
int n, m, p[N];
char s[N][8];
int get_dist(int i, int j)
{
    int cnt = 0;
    for (int k = 0; k < 7; ++k)
        if (s[i][k] != s[j][k])
            ++cnt;
    return cnt;
}
struct edge
{
    int w, u, v;
    bool operator<(const edge &a) const { return w < a.w; }
} e[N * N];
int find(int x)
{
    return p[x] == x ? x : p[x] = find(p[x]);
}
int kruskal()
{
    int res = 0;
    for (int i = 0; i < n; ++i)
        p[i] = i;
    sort(e, e + m);
    for (int i = 0; i < m; ++i)
    {
        int a = find(e[i].u), b = find(e[i].v);
        if (a != b)
            p[a] = b, res += e[i].w;
    }
    return res;
}
int main()
{
    while (scanf("%d", &n), n)
    {
        m = 0;
        for (int i = 0; i < n; ++i)
            scanf("%s", s[i]);
        for (int i = 0; i < n; ++i)
            for (int j = i + 1; j < n; ++j)
                e[m++] = {get_dist(i, j), i, j};
        printf("The highest possible quality is 1/%d.\n", kruskal());
    }
    return 0;
}
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
#include <cstdio>
#include <algorithm>
#define N 2000
using namespace std;
int n, g[N][N], d[N];
char s[N][8];
bool st[N];
int get_dist(int i, int j)
{
    int cnt = 0;
    for (int k = 0; k < 7; ++k)
        if (s[i][k] != s[j][k])
            ++cnt;
    return cnt;
}
int prim()
{
    int res = 0;
    for (int i = 0; i < n; ++i)
        d[i] = 0x3f3f3f3f, st[i] = 0;
    d[0] = 0;
    for (int i = 0; i < n; ++i)
    {
        int t = -1;
        for (int j = 0; j < n; ++j)
            if (!st[j] && (t == -1 || d[j] < d[t]))
                t = j;
        st[t] = 1;
        if (i)
            res += d[t];
        for (int j = 0; j < n; ++j)
            if (!st[j] && d[j] > g[t][j])
                d[j] = g[t][j];
    }
    return res;
}
int main()
{
    while (scanf("%d", &n), n)
    {
        for (int i = 0; i < n; ++i)
            scanf("%s", s[i]);
        for (int i = 0; i < n; ++i)
            for (int j = i + 1; j < n; ++j)
                g[i][j] = g[j][i] = get_dist(i, j);
        printf("The highest possible quality is 1/%d.\n", prim());
    }
    return 0;
}

POJ-2349 Arctic Network

求最小生成树中的最大边，有人称其为瓶颈生成树。

  1. 有 s 个卫星，且卫星间通信成本为 0。
  2. 所以最小生成树可以剔除 s-1 个点，只需要留下 1 个卫星与最小生成树包含的点集通信。
  3. 方案：跑一边 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
#include <cstdio>
#include <cmath>
#include <algorithm>
#define N 500
using namespace std;
int t, s, n, m, x[N], y[N], p[N];
double get_dist(int i, int j)
{
    return sqrt(pow(x[i] - x[j], 2) + pow(y[i] - y[j], 2));
}
struct edge
{
    double w;
    int u, v;
    bool operator<(const edge &a) const { return w < a.w; }
} e[N * N];
int find(int x)
{
    return p[x] == x ? x : p[x] = find(p[x]);
}
double kruskal()
{
    double res = 0;
    for (int i = 0; i < n; ++i)
        p[i] = i;
    sort(e, e + m);
    for (int i = 0, cnt = 0; i < m; ++i)
    {
        int a = find(e[i].u), b = find(e[i].v);
        if (a != b)
        {
            p[a] = b, res = e[i].w, ++cnt;
            if (cnt + s >= n) // (cnt + 1) + (s - 1) >= n
                break;
        }
    }
    return res;
}
int main()
{
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d%d", &s, &n);
        for (int i = 0; i < n; ++i)
            scanf("%d%d", x + i, y + i);
        if (n <= s)
            printf("%.2lf", 0);
        else
        {
            m = 0;
            for (int i = 0; i < n; ++i)
                for (int j = i + 1; j < n; ++j)
                    e[m++] = {get_dist(i, j), i, j};
            printf("%.2lf\n", kruskal());
        }
    }
    return 0;
}
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
#include <cstdio>
#include <cmath>
#include <algorithm>
#define N 500
using namespace std;
int t, s, n, x[N], y[N];
double g[N][N], d[N];
bool st[N];
double get_dist(int i, int j)
{
    return sqrt(pow(x[i] - x[j], 2) + pow(y[i] - y[j], 2));
}
double prim()
{
    for (int i = 0; i < n; ++i)
        d[i] = 1e19, st[i] = 0;
    d[0] = 0;
    for (int i = 0; i < n; ++i)
    {
        int t = -1;
        for (int j = 0; j < n; ++j)
            if (!st[j] && (t == -1 || d[j] < d[t]))
                t = j;
        st[t] = 1;
        for (int j = 0; j < n; ++j)
            if (!st[j] && d[j] > g[t][j])
                d[j] = g[t][j];
    }
    sort(d + 1, d + n);
    return d[n - s];
}
int main()
{
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d%d", &s, &n);
        for (int i = 0; i < n; ++i)
            scanf("%d%d", x + i, y + i);
        if (n <= s)
            printf("%.2lf", 0);
        else
        {
            for (int i = 0; i < n; ++i)
            for (int j = i + 1; j < n; ++j)
                g[i][j] = g[j][i] = get_dist(i, j);
            printf("%.2lf\n", prim());
        }
    }
    return 0;
}

POJ-1751 Highways

最小生成树问题。建图时，已经修好的高速公路可以

  1. Kruskal, 合并边上两点（p[find(u)] = find(v)）；
  2. Prim, 边长设置为 0（g[u][v] = g[v][u] = 0）。

然后再跑 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
#include <cstdio>
#include <cmath>
#include <algorithm>
#define N 751
using namespace std;
int n, m, a, b, x[N], y[N], p[N];
double get_dist(int i, int j)
{
    return sqrt(pow(x[i] - x[j], 2) + pow(y[i] - y[j], 2));
}
struct edge
{
    double w;
    int u, v;
    bool operator<(const edge &a) const { return w < a.w; }
} e[N * N];
int find(int x)
{
    return p[x] == x ? x : p[x] = find(p[x]);
}
void kruskal()
{
    sort(e, e + m);
    for (int i = 0; i < m; ++i)
    {
        int a = find(e[i].u), b = find(e[i].v);
        if (a != b)
        {
            p[a] = b;
            printf("%d %d\n", e[i].u, e[i].v);
        }
    }
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d%d", x + i, y + i);
    for (int i = 1; i <= n; ++i)
        p[i] = i;
    scanf("%d", &m);
    while (m--)
    {
        scanf("%d%d", &a, &b);
        p[find(a)] = find(b);
    }
    m = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j)
            e[m++] = {get_dist(i, j), i, j};
    kruskal();
    return 0;
}
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
#include <cstdio>
#include <cmath>
#include <algorithm>
#define N 751
using namespace std;
int n, m, a, b, x[N], y[N], path[N];
double g[N][N], d[N];
bool st[N];
double get_dist(int i, int j)
{
    return sqrt(pow(x[i] - x[j], 2) + pow(y[i] - y[j], 2));
}
void prim()
{
    for (int i = 1; i <= n; ++i)
        d[i] = 1e16, st[i] = 0;
    d[1] = 0;
    for (int i = 0; i < n; ++i)
    {
        int t = -1;
        for (int j = 1; j <= n; ++j)
            if (!st[j] && (t == -1 || d[j] < d[t]))
                t = j;
        st[t] = 1;
        if (i && g[path[t]][t] != 0)
            printf("%d %d\n", path[t], t);
        for (int j = 1; j <= n; ++j)
            if (!st[j] && d[j] > g[t][j])
                d[j] = g[t][j], path[j] = t;
    }
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d%d", x + i, y + i);
    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j)
            g[i][j] = g[j][i] = get_dist(i, j);
    scanf("%d", &m);
    while (m--)
    {
        scanf("%d%d", &a, &b);
        g[a][b] = g[b][a] = 0;
    }
    prim();
    return 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
#include <cstdio>
#include <cmath>
#include <algorithm>
#define N 100
using namespace std;
int n, m, g[N][N], p[N];
struct edge
{
    int w, u, v;
    bool operator<(const edge &a) const { return w < a.w; }
} e[N * N];
int find(int x)
{
    return p[x] == x ? x : p[x] = find(p[x]);
}
int kruskal()
{
    int res = 0;
    for (int i = 0; i < n; ++i)
        p[i] = i;
    sort(e, e + m);
    for (int i = 0; i < m; ++i)
    {
        int a = find(e[i].u), b = find(e[i].v);
        if (a != b)
            p[a] = b, res += e[i].w;
    }
    return res;
}
int main()
{
    while (~scanf("%d", &n))
    {
        m = 0;
        for (int i = 0, w; i < n; ++i)
            for (int j = 0; j < n; ++j)
            {
                scanf("%d", &w);
                if (i > j)
                    e[m++] = {w, i, j};
            }
        printf("%d\n", kruskal());
    }
    return 0;
}
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
#include <cstdio>
#include <algorithm>
#define N 100
using namespace std;
int n, g[N][N], d[N];
bool st[N];
int prim()
{
    int res = 0;
    for (int i = 0; i < n; ++i)
        d[i] = 0x3f3f3f3f, st[i] = 0;
    d[0] = 0;
    for (int i = 0; i < n; ++i)
    {
        int t = -1;
        for (int j = 0; j < n; ++j)
            if (!st[j] && (t == -1 || d[j] < d[t]))
                t = j;
        st[t] = 1;
        if (i)
            res += d[t];
        for (int j = 0; j < n; ++j)
            if (!st[j] && d[j] > g[t][j])
                d[j] = g[t][j];
    }
    return res;
}
int main()
{
    while (~scanf("%d", &n))
    {
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                scanf("%d", &g[i][j]);
        printf("%d\n", prim());
    }
    return 0;
}

POJ-3026 Borg Maze

这题麻烦的点在于需要先建图。以 S 和所有 A 为起点，跑几遍 BFS 建图。然后再跑 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
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 50, M = 10000;
int t, r, c, n, m, p[N * N], ds[] = {1, 0, -1, 0, 1};
string maze[N];
bool st[N][N];
int q[N * N][2], hh, tt, w;
struct edge
{
    int w, u, v;
    bool operator<(const edge &a) const { return w < a.w; }
} e[M];
int find(int x)
{
    return p[x] == x ? x : p[x] = find(p[x]);
}
int kruskal()
{
    int res = 0;
    for (int i = 0; i < r * c; ++i)
        p[i] = i;
    sort(e, e + m);
    for (int i = 0; i < m; ++i)
    {
        int a = find(e[i].u), b = find(e[i].v);
        if (a != b)
            p[a] = b, res += e[i].w;
    }
    return res;
}
void bfs(int x, int y)
{
    int src = x * c + y;
    hh = tt = 0;
    q[tt][0] = x, q[tt][1] = y, tt++;
    for (int i = 0; i < r; ++i)
        for (int j = 0; j < c; ++j)
            st[i][j] = 0;
    st[x][y] = 1;
    maze[x][y] = ' ';
    w = 0;
    while (tt - hh)
    {
        ++w;
        int sz = tt - hh;
        while (sz--)
        {
            int a = q[hh][0], b = q[hh][1];
            ++hh;
            for (int i = 0; i < 4; ++i)
            {
                int nx = a + ds[i], ny = b + ds[i + 1];
                if (nx < 0 || nx >= r || ny < 0 || ny >= c || //
                    maze[nx][ny] == '#' || st[nx][ny])
                    continue;
                if (maze[nx][ny] != ' ')
                    e[m++] = {w, src, nx * c + ny};
                q[tt][0] = nx, q[tt][1] = ny, tt++;
                st[nx][ny] = 1;
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> t;
    while (t--)
    {
        cin >> c >> r;
        getline(cin, maze[0]); // consume '\n'.
        for (int i = 0; i < r; ++i)
            getline(cin, maze[i]);
        n = m = 0;
        for (int i = 0; i < r; ++i)
            for (int j = 0; j < c; ++j)
                if (maze[i][j] == 'S' || maze[i][j] == 'A')
                    ++n, bfs(i, j);
        cout << kruskal() << endl;
    }
    return 0;
}
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
#include <iostream>
#include <map>
using namespace std;
const int N = 51, P = 101;
int t, r, c, n, g[P][P], d[P], ds[] = {1, 0, -1, 0, 1};
string maze[N];
bool st[N * N];
int q[N * N][2], hh, tt, w;
map<int, int> m;
int prim()
{
    int res = 0;
    for (int i = 0; i < n; ++i)
        d[i] = 0x3f3f3f3f, st[i] = 0;
    d[0] = 0;
    for (int i = 0; i < n; ++i)
    {
        int t = -1;
        for (int j = 0; j < n; ++j)
            if (!st[j] && (t == -1 || d[j] < d[t]))
                t = j;
        st[t] = 1;
        if (i)
            res += d[t];
        for (int j = 0; j < n; ++j)
            if (!st[j] && d[j] > g[t][j])
                d[j] = g[t][j];
    }
    return res;
}
int to_idx(int x, int y)
{
    int pos = x * c + y;
    if (m.find(pos) == m.end())
        m[pos] = n++;
    return m[pos];
}
void bfs(int x, int y)
{
    int src = x * c + y, src_idx = to_idx(x, y);
    hh = tt = 0;
    q[tt][0] = x, q[tt][1] = y, tt++;
    for (int i = 0; i < r * c; ++i)
        st[i] = 0;
    st[src] = 1;
    maze[x][y] = ' ';
    w = 0;
    while (tt - hh)
    {
        ++w;
        int sz = tt - hh;
        while (sz--)
        {
            int a = q[hh][0], b = q[hh][1];
            ++hh;
            for (int i = 0; i < 4; ++i)
            {
                int nx = a + ds[i], ny = b + ds[i + 1], dest = nx * c + ny;
                if (nx < 0 || nx >= r || ny < 0 || ny >= c || //
                    maze[nx][ny] == '#' || st[dest])
                    continue;
                if (maze[nx][ny] != ' ')
                {
                    int dest_idx = to_idx(nx, ny);
                    g[src_idx][dest_idx] = g[dest_idx][src_idx] = w;
                }
                q[tt][0] = nx, q[tt][1] = ny, tt++;
                st[dest] = 1;
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> t;
    while (t--)
    {
        cin >> c >> r;
        getline(cin, maze[0]); // consume '\n'.
        for (int i = 0; i < r; ++i)
            getline(cin, maze[i]);
        n = 0;
        m.clear();
        for (int i = 0; i < r; ++i)
            for (int j = 0; j < c; ++j)
                if (maze[i][j] == 'S' || maze[i][j] == 'A')
                    bfs(i, j);
        cout << prim() << endl;
    }
    return 0;
}

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
#include <cstdio>
#include <algorithm>
#define N 101
using namespace std;
int t, n, m, p[N];
struct edge
{
    int w, u, v;
    bool operator<(const edge &a) const { return w < a.w; }
} e[N * N];
int find(int x)
{
    return p[x] == x ? x : p[x] = find(p[x]);
}
void kruskal()
{
    int sum = 0, res = 0;
    for (int i = 1; i <= n; ++i)
        p[i] = i;
    sort(e, e + m);
    for (int i = 0; i < m; ++i)
    {
        int r = i;
        while (r < m && e[i].w == e[r].w)
            ++r;
        --r;
        for (int j = i; j <= r; ++j)
        {
            int a = find(e[j].u), b = find(e[j].v);

            if (a != b)
                sum += e[j].w;
        }
        for (int j = i; j <= r; ++j)
        {
            int a = find(e[j].u), b = find(e[j].v);
            if (a != b)
                p[a] = b, res += e[j].w;
        }
        i = r;
    }
    if (sum != res)
        printf("Not Unique!\n");
    else
        printf("%d\n", res);
}
int main()
{
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d%d", &n, &m);
        for (int i = 0; i < m; ++i)
            scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
        kruskal();
    }
    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
#include <cstdio>
#include <cmath>
#include <algorithm>
#define N 101
using namespace std;
int n, m, p[N];
struct edge
{
    int w, u, v;
    bool operator<(const edge &a) const { return w < a.w; }
} e[N * N];
int find(int x)
{
    return p[x] == x ? x : p[x] = find(p[x]);
}
int kruskal()
{
    int res = 0;
    for (int i = 1; i <= n; ++i)
        p[i] = i;
    sort(e, e + m);
    for (int i = 0; i < m; ++i)
    {
        int a = find(e[i].u), b = find(e[i].v);
        if (a != b)
            p[a] = b, res += e[i].w;
    }
    return res;
}
int main()
{
    while (~scanf("%d", &n) && n)
    {
        m = n * (n - 1) / 2;
        for (int i = 0, w; i < m; ++i)
            scanf("%d %d %d", &e[i].u, &e[i].v, &e[i].w);
        printf("%d\n", kruskal());
    }
    return 0;
}
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
#include <cstdio>
#include <algorithm>
#define N 101
using namespace std;
int n, g[N][N], d[N];
bool st[N];
int prim()
{
    int res = 0;
    for (int i = 1; i <= n; ++i)
        d[i] = 0x3f3f3f3f, st[i] = 0;
    d[0] = 0;
    for (int i = 0; i < n; ++i)
    {
        int t = -1;
        for (int j = 1; j <= n; ++j)
            if (!st[j] && (t == -1 || d[j] < d[t]))
                t = j;
        st[t] = 1;
        if (i)
            res += d[t];
        for (int j = 1; j <= n; ++j)
            if (!st[j] && d[j] > g[t][j])
                d[j] = g[t][j];
    }
    return res;
}
int main()
{
    while (~scanf("%d", &n) && n)
    {
        for (int i = 0, a, b, c; i < n * (n - 1) / 2; ++i)
        {
            scanf("%d%d%d", &a, &b, &c);
            g[a][b] = g[b][a] = c;
        }
        printf("%d\n", prim());
    }
    return 0;
}

HDU-1875 畅通工程再续

  1. 计算点距离，建图。
  2. 跑 MST 时，不满足的边不纳入考虑。
  3. Kruskal 跑不够 n - 1 条边，或者 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
#include <cstdio>
#include <cmath>
#include <algorithm>
#define N 100
using namespace std;
int t, n, m, x[N], y[N], p[N];
double get_dist(int i, int j)
{
    return sqrt(pow(x[i] - x[j], 2) + pow(y[i] - y[j], 2));
}
struct edge
{
    double w;
    int u, v;
    bool operator<(const edge &a) const { return w < a.w; }
} e[N * N];
int find(int x)
{
    return p[x] == x ? x : p[x] = find(p[x]);
}
void kruskal()
{
    double res = 0;
    int cnt = 0;
    for (int i = 0; i < n; ++i)
        p[i] = i;
    sort(e, e + m);
    for (int i = 0; i < m; ++i)
    {
        int a = find(e[i].u), b = find(e[i].v);
        double w = e[i].w;
        if (a != b && 10 <= w && w <= 1000)
            p[a] = b, res += e[i].w, ++cnt;
        if (cnt + (m - i - 1) < n - 1)
            break;
    }
    if (cnt == n - 1)
        printf("%.1lf\n", res * 100);
    else
        printf("oh!\n");
}
int main()
{
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &n);
        for (int i = 0; i < n; ++i)
            scanf("%d%d", x + i, y + i);
        m = 0;
        for (int i = 0; i < n; ++i)
            for (int j = i + 1; j < n; ++j)
                e[m++] = {get_dist(i, j), i, j};
        kruskal();
    }
    return 0;
}
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
#include <cstdio>
#include <cmath>
#include <algorithm>
#define N 100
#define INF 1e18
using namespace std;
int t, n, m, x[N], y[N];
double g[N][N], d[N];
bool st[N];
double get_dist(int i, int j)
{
    return sqrt(pow(x[i] - x[j], 2) + pow(y[i] - y[j], 2));
}
void prim()
{
    double res = 0;
    int cnt = 0;
    for (int i = 0; i < n; ++i)
        d[i] = INF, st[i] = 0;
    d[0] = 0;
    for (int i = 0; i < n; ++i)
    {
        int t = -1;
        for (int j = 0; j < n; ++j)
            if (!st[j] && (t == -1 || d[j] < d[t]))
                t = j;
        st[t] = 1;
        if (i)
        {
            if (d[t] == INF)
            {
                printf("oh!\n");
                return;
            }
            res += d[t];
        }
        for (int j = 0; j < n; ++j)
            if (!st[j] && d[j] > g[t][j] && 10 <= g[t][j] && g[t][j] <= 1000)
                d[j] = g[t][j];
    }
    printf("%.1lf\n", res * 100);
}
int main()
{
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &n);
        for (int i = 0; i < n; ++i)
            scanf("%d%d", x + i, y + i);
        m = 0;
        for (int i = 0; i < n; ++i)
            for (int j = i + 1; j < n; ++j)
                g[i][j] = g[j][i] = get_dist(i, j);
        prim();
    }
    return 0;
}