Krusal 时间复杂度 $O(m\log m)$

  Prim 时间复杂度 $O(n^2)$，二叉堆优化至 $O(m\log n)$。Prim 主要用于稠密图。

1. POJ1251 Jungle Roads

题目链接

题意：给出 n 个村庄，n - 1 个村庄连接的村庄以及道路及其每月维护费，求使村庄连通的每月最小花费。

  模板题，上网查了才发现一直 RE 是 scanf 的锅。

 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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 30, M = 1005;

struct edge {
    int u, v, w;
    edge() {}
    edge(int u, int v, int w) : u(u), v(v), w(w) {}
    friend bool operator < (edge a, edge b) {
        return a.w < b.w;
    }
}e[M];

int n, m;
int fa[N];

int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

int krusal() {
    sort(e + 1, e + m + 1);
    int ans = 0, cnt = 0;
    for (int i = 1; i <= n; ++i) fa[i] = i;
    for (int i = 1; i <= m; ++i) {
        int x = find(e[i].u);
        int y = find(e[i].v);
        if (x != y) {
            ans += e[i].w;
            fa[x] = y;
            cnt++;
        }
        if (cnt == n - 1) break;
    }
    if (cnt < n - 1) return -1;
    return ans;
}

int main() 
{
    while (scanf("%d", &n), n) {
        m = 0;
        for (int i = 1; i < n; ++i) {
            char c;
            int k, x, y;
            cin >> c >> k;
            x = c - 'A' + 1;
            while (k--) {
                cin >> c >> y;
                e[++m] = edge(x, c - 'A' + 1, y);
            }
        }
        printf("%d\n", krusal());
    }
    return 0;
}

2. POJ1287 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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 55, M = 1505;

struct edge {
    int u, v, w;
    edge() {}
    edge(int u, int v, int w) : u(u), v(v), w(w) {}
    friend bool operator < (edge a, edge b) {
        return a.w < b.w;
    }
}e[M];

int n, m;
int fa[N];

int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

int krusal() {
    sort(e + 1, e + m + 1);
    int ans = 0, cnt = 0;
    for (int i = 1; i <= n; ++i) fa[i] = i;
    for (int i = 1; i <= m; ++i) {
        int x = find(e[i].u);
        int y = find(e[i].v);
        if (x != y) {
            ans += e[i].w;
            fa[x] = y;
            cnt++;
        } 
        if (cnt == n - 1) break;
    }
    if (cnt < n - 1) return -1;
    return ans;
}

int main() 
{
    while (scanf("%d", &n), n) {
        scanf("%d", &m);
        int x, y, z;
        for (int i = 1; i <= m; ++i) {
            scanf("%d%d%d", &x, &y, &z);
            e[i] = edge(x, y, z);
        }
        printf("%d\n", krusal());
    }
    return 0;
}

3. POJ2031 Building a Space Station

题目链接

题意：三维空间中给出 n 个球体的坐标和半径，如果球体未相通，需要建立一些通道连接所有球体，表面相切可认为相通，求通道的最短距离。

  任意两个球相交距离为0，不相交圆心之间距离减去半径和为距离，用最小生成树做即可，G++ 用 double 会 Wa

 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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int N = 105;
const double INF = 0x3f3f3f3f;

struct point {
    double x, y, z;
    double r;
}p[N];

int n;
double a[N][N];
double d[N];
int v[N];

double dis(point a, point b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) + (a.z - b.z) * (a.z - b.z));
}

void prim() {
    for (int i = 1; i <= n; ++i) d[i] = INF;
    memset(v, 0, sizeof(v));
    d[1] = 0;
    for (int i = 1; i < n; ++i) {
        int x = 0;
        for (int j = 1; j <= n; ++j)
            if (!v[j] && (x == 0 || d[j] < d[x])) x = j;
        v[x] = 1;
        for (int y = 1; y <= n; ++y)
            if (!v[y]) d[y] = min(d[y], a[x][y]);
    }
}

int main() 
{
    while (scanf("%d", &n), n) {
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j) a[i][j] = INF;
        for (int i = 1; i <= n; ++i) a[i][i] = 0;
        for (int i = 1; i <= n; ++i) {
            scanf("%lf%lf%lf%lf", &p[i].x, &p[i].y, &p[i].z, &p[i].r);
        }
        for (int i = 1; i < n; ++i) {
            for (int j = i + 1; j <= n; ++j) {
                a[i][j] = a[j][i] = max(0.0, dis(p[i], p[j]) - p[i].r - p[j].r);
            }
        }
        prim();
        double ans = 0;
        for (int i = 2; i <= n; ++i) ans += d[i];
        printf("%.3lf\n", ans);
    }
    return 0;
}

4. POJ2421 Constructing Roads

题目链接

题意：给出 $n$ 个点和 $n\times n$ 的邻接矩阵，q 条已连好的边，求使点连通还需建立道路长度最小值。

  适合用 krusal，已经连通的点先合并。

 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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 105;

struct edge {
    int u, v, w;
    friend bool operator < (edge a, edge b) {
        return a.w < b.w;
    }
}e[N * N];

int n, tot, q, cnt;
int fa[N];

int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

void unite(int x, int y) {
    int fx = find(x);
    int fy = find(y);
    if (fx == fy) return;
    fa[fx] = fy;
    cnt++;
}

int krusal() {
    sort(e + 1, e + tot + 1);
    int ans = 0;
    for (int i = 1; i <= tot; ++i) {
        if (find(e[i].u) != find(e[i].v)) {
            unite(e[i].u, e[i].v);
            ans += e[i].w;
        }
        if (cnt == n - 1) break;
    }
    if (cnt < n - 1) return -1;
    return ans;
}

int main() 
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) fa[i] = i;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            scanf("%d", &e[++tot].w);
            e[tot].u = i;
            e[tot].v = j;
        }
    }
    scanf("%d", &q);
    int a, b;
    while (q--) {
        scanf("%d%d", &a, &b);
        unite(a, b);
    }
    printf("%d\n", krusal());
    return 0;
}

5. ZOJ1586 QS Network

题目链接

题意：有一种叫 QS 的智能生物，两个 QS 想要连接，需要购买两个网络适配器和一段网络电缆，一个网络适配器只能只能在单个连接中使用。通信过程中，QS 将消息广播到它所有连接的 QS，接收到消息的 QS 将消息广播到所有连接的 QS，直到所有 QS 收到消息。给出 QS 数目 n，每个 QS 网络适配器价格，$n\times n$ 矩阵，i 行 j 列 表示 i,j 之间电缆费用，求连通 n 个点最小花费。

  网络适配器价格加入边中，用 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 <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f, N = 1005;

int t, n;
int a[N], g[N][N];
int d[N], v[N];

int prim() {
    priority_queue<P, vector<P>, greater<P> > q;
    memset(d, 0x3f, sizeof(d));
    memset(v, 0, sizeof(v));
    int ans = 0;
    d[1] = 0;
    q.push(P(0, 1));
    while (!q.empty()) {
        int x = q.top().second;
        q.pop();
        if (v[x]) continue;
        v[x] = 1;
        ans += d[x];
        for (int y = 1; y <= n; ++y) {
            if (!v[y] && d[y] > g[x][y]) {
                d[y] = g[x][y];
                q.push(P(d[y], y));
            }
        }
    }
    return ans;
}

int main() 
{
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                scanf("%d", &g[i][j]);
                g[i][j] += a[i] + a[j];
            }
        }
        printf("%d\n", prim());
    }
    return 0;
}

6. POJ1789 Truck History

题目链接

题意：7 个小写字母表示一个编码，编码距离的定义为 7 个位置上不同字符的个数，n 个编码，求连接所有编码的最短距离。

 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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 2005;

int n;
int d[N], v[N], a[N][N];
char str[N][10];

void prim() {
    memset(d, 0x3f, sizeof(d));
    memset(v, 0, sizeof(v));
    d[1] = 0;
    for (int i = 1; i < n; ++i) {
        int x = 0;
        for (int j = 1; j <= n; ++j)
            if (!v[j] && (x == 0 || d[j] < d[x])) x = j;
        v[x] = 1;
        for (int y = 1; y <= n; ++y)
            if (!v[y]) d[y] = min(d[y], a[x][y]);
    }
}

int main() 
{
    while (scanf("%d", &n), n) {
        for (int i = 1; i <= n; ++i) {
            scanf("%s", str[i]);
        }
        for (int i = 1; i <= n; ++i) {
            a[i][i] = 0;
            for (int j = i + 1; j <= n; ++j) {
                int cnt = 0;
                for (int k = 0; k < 7; ++k)
                    if (str[i][k] != str[j][k]) cnt++;
                a[i][j] = a[j][i] = cnt;
            }
        }
        prim();
        int ans = 0;
        for (int i = 1; i <= n; ++i) ans += d[i];
        printf("The highest possible quality is 1/%d.\n", ans);
    }
    return 0;
}

7. POJ2349 Arctic Network

题目连接

题意：s 个卫星频道，p 个前哨站，给出前哨站坐标，两个前哨站可以通过卫星频道或无线电通信，卫星频道无视距离，无线电两者距离不能超过 d，所有前哨站可以直接或间接通信情况下，求 d 的最小值。

  最小生成树求出 p - 1 条边从小到大排序，后 s - 1 条用卫星通信，输出第 p - s 条边，即 d[n - m + 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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int N = 505;
const double INF = 0x3f3f3f3f;

struct point {
    int x, y;
}p[N];

int t, m, n;
double g[N][N];
double d[N];
int v[N];

double dis(point a, point b) {
    return sqrt((a.x - b.x) * (a.x - b.x) / 1.00 + (a.y - b.y) * (a.y - b.y) / 1.0);
}

void prim() {
    for (int i = 0; i <= n; ++i) d[i] = INF;
    memset(v, 0, sizeof(v));
    d[1] = 0.0;
    for (int i = 1; i < n; ++i) {
        int x = 0;
        for (int j = 1; j <= n; ++j) 
            if (!v[j] && (x == 0 || d[j] < d[x])) x = j;
        v[x] = 1;
        for (int y = 1; y <= n; ++y)
            if (!v[y]) d[y] = min(d[y], g[x][y]); 
    }
}

int main() 
{
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &m, &n);
        for (int i = 1; i <= n; ++i) {
            scanf("%d%d", &p[i].x, &p[i].y);
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = i + 1; j <= n; ++j) {
                double l = dis(p[i], p[j]);
                g[i][j] = g[j][i] = l;
            }
        }
        prim();
        sort(d + 1, d + n + 1);
        printf("%.2lf\n", d[n - m + 1]);
    }
    return 0;
}

8. POJ1751 Highways

题目链接

题意：给出 n 个城镇及其坐标，已经修好的 m 条告诉公路，为使所有城镇连通，求还需修建高速公路的最小长度。

  已存在的边权为 0，用 pre 记录相邻结点。

 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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
typedef pair<double, int> P;
const int N = 755;
const double INF = 0x3f3f3f3f, eps = 1e-8;

int n, m;
int x[N], y[N], vis[N], pre[N];
double g[N][N], d[N];

void prim() {
    priority_queue<P, vector<P>, greater<P> > q;
    for (int i = 1; i <= n; ++i) d[i] = INF;
    memset(vis, 0, sizeof(vis));
    d[1] = 0;
    q.push(P(0, 1));
    while (!q.empty()) {
        int u = q.top().second;
        q.pop();
        if (!vis[u]) vis[u] = 1;; 
        for (int v = 1; v <= n; ++v) {
            if (!vis[v] && d[v] > g[u][v]) {
                d[v] = g[u][v];
                pre[v] = u;
                q.push(P(d[v], 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) {
        for (int j = i + 1; j <= n; ++j) {
            double l = sqrt(1.0 * (x[i] - x[j]) * (x[i] - x[j]) + 1.0 * (y[i] - y[j]) * (y[i] - y[j]));
            g[i][j] = g[j][i] = l;
            
        }
    }
    scanf("%d", &m);
    while (m--) {
        int a, b;
        scanf("%d%d", &a, &b);
        g[a][b] = g[b][a] = 0.0;
    }
    prim();
    for (int i = 2; i <= n; ++i) {
        if (g[pre[i]][i] > eps) {
            printf("%d %d\n", pre[i], i);
        }
    }
    return 0;
}

9. POJ1258 Agri-Net

题目链接

题意：$n\times n(3\le n\le100)$ 的邻接矩阵，表示 $n$ 个村庄之间的距离，Farmer Jorn 要把所有村庄连接起来，求最短距离。

 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 <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f, N = 105;

int n;
int a[N][N];
int d[N], v[N];

int prim() {
    priority_queue<P, vector<P>, greater<P> > q;
    memset(d, 0x3f, sizeof(d));
    memset(v, 0, sizeof(v));
    int ans = 0;
    d[1] = 0;
    q.push(P(0, 1));
    while (!q.empty()) {
        int x = q.top().second;
        q.pop();
        if (v[x]) continue;
        v[x] = 1;
        ans += d[x];
        for (int y = 1; y <= n; ++y) {
            if (!v[y] && d[y] > a[x][y]) {
                d[y] = a[x][y];
                q.push(P(d[y], y));
            }
        }
    }
    return ans;
}

int main() 
{
    while (~scanf("%d", &n)) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                scanf("%d", &a[i][j]);
            }
        }
        printf("%d\n", prim());
    }
    return 0;
}

10. POJ3026 Borg Maze

题目链接

题意：Borg 是一种强大的类机器人种族，在迷宫中帮助 Borg 找出最小的距离同化外星人，每当一个外星人被同化或者在搜索起点，集团可能会分裂成两个或以上集团。

  bfs 每个 A 点与 S 点到其他点距离建图，之后用 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
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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f, N = 105, M = 55;

struct node {
    int x, y, step, id;
    node() {}
    node(int x, int y, int step, int id) : x(x), y(y), step(step) {}
}p[N];

int t, m, n, cnt;
int d[N], g[N][N], vis2[N];
int vis1[M][M], mp[M][M];
char s[M][M];
int dx[] = {1, -1, 0, 0};
int dy[] = {0 , 0, 1, -1};

void bfs(int st) {
    memset(vis1, 0, sizeof(vis1));
    queue<node> q;
    q.push(p[st]);
    vis1[p[st].x][p[st].y] = 1;
    while (!q.empty()) {
        node u = q.front();
        q.pop();
        g[st][mp[u.x][u.y]] = u.step;
        for (int i = 0; i < 4; ++i) {
            int tx = u.x + dx[i];
            int ty = u.y + dy[i];
            if (tx > 0 && tx <= n && ty > 0 && ty <= m && s[tx][ty] != '#' && !vis1[tx][ty]) {
                q.push(node(tx, ty, u.step + 1));
                vis1[tx][ty] = 1;
            }
        }
    }
}

int prim() {
    memset(d, 0x3f, sizeof(d));
    memset(vis2, 0, sizeof(vis2));
    priority_queue<P, vector<P>, greater<P> > q;
    int ans = 0;
    d[1] = 0;
    q.push(P(0, 1));
    while (!q.empty()) {
        int u = q.top().second;
        q.pop();
        if (!vis2[u]) {
            vis2[u] = 1;
            ans += d[u];
        }
        for (int v = 1; v <= cnt; ++v) {
            if (!vis2[v] && d[v] > g[u][v]) {
                d[v] = g[u][v];
                q.push(P(d[v], v));
            }
        }
    }
    return ans;
}

int main() 
{
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &m, &n);
        memset(mp, 0, sizeof(mp));
        cnt = 0;
        gets(s[0]);
        for (int i = 1; i <= n; ++i) {
            gets(s[i] + 1);
            for (int j = 1; j <= m; ++j) {
                if (s[i][j] == 'A' || s[i][j] == 'S') {
                    p[++cnt] = node(i, j, 0);
                    mp[i][j] = cnt;
                }
            }
        }
        for (int i = 1; i <= cnt; ++i) {
            bfs(i);
        }
        printf("%d\n", prim());
    }
    return 0;
}

11. POJ1679 The Unique MST

题目链接

题意：给定连通无向图，判断最小生成树是否唯一。

  枚举最小生成树的每一条边，删除后求最小生成树，结果相同不唯一，删除边后 krusal 里 cnt < n - 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
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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 105, M = 1e4 + 5;

struct edge {
    int u, v, w;
    friend bool operator < (edge a, edge b) {
        return a.w < b.w;
    }
}e[M];

int t, n, m;
int fa[N], sta[N], top;

int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

int krusal(int num) {
    int cnt = 0, ans = 0, tot = 0;
    for (int i = 1; i <= n; ++i) fa[i] = i;
    for (int i = 1; i <= m; ++i) {
        if (i == num) continue;
        int x = find(e[i].u);
        int y = find(e[i].v);
        if (x != y) {
            fa[x] = y;
            ans += e[i].w;
            cnt++;
            if (!num) sta[++top] = i;
        }
        if (cnt == n - 1) break;
    }
    if (cnt < n - 1) return -1;
    return ans;
}

int main() 
{
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= m; ++i) {
            scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
        }
        sort(e + 1, e + m + 1);
        top = 0;
        int ans = krusal(0);
        int flag = 0;
        for (int i = 1; i <= top; ++i) {
            int res = krusal(sta[i]);
            if (res == ans) { flag = 1; break; }
        }
        if (flag) puts("Not Unique!");
        else printf("%d\n", ans);
    }
    return 0;
}

12. HDU1233 还是畅通工程

题目链接

题意：求最小生成树。

  模板题，完全图用 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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f, N = 105;

int n, m;
int d[N], vis[N], g[N][N];

int prim() {
    memset(d, 0x3f, sizeof(d));
    memset(vis, 0, sizeof(vis));
    priority_queue<P, vector<P>, greater<P> > q;
    int ans = 0;
    d[1] = 0;
    q.push(P(0, 1));
    while (!q.empty()) {
        int x = q.top().second;
        q.pop();
        if (!vis[x]) {
            vis[x] = 1;
            ans += d[x];
        }
        for (int y = 1; y <= n; ++y) {
            if (!vis[y] && d[y] > g[x][y]) {
                d[y] = g[x][y];
                q.push(P(d[y], y));
            }
        }
    }
    return ans;
}

int main() 
{
    while (scanf("%d", &n), n) {
        m = n * (n - 1) / 2;
        int x, y, z;
        for (int i = 1; i <= m; ++i) {
            scanf("%d%d%d", &x, &y, &z);
            g[x][y] = g[y][x] = z;
        }
        printf("%d\n", prim());
    }
    return 0;
}

13. HDU1301 Jungle Roads

题目链接

  和第一题完全一样。

14. HDU1875 畅通工程再续

题目链接

题意：给出 n 个小岛坐标，在小岛间建桥连通所有岛，条件是小岛间距离属于 $[10,1000]$，价格 100 元/米，求最小造价。

 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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
typedef pair<double, int> P;
const int N = 105;
const double INF = 0x3f3f3f3f;

struct point {
    int x, y;
}p[N];

int t, n;
int vis[N];
double d[N], g[N][N];

double dis(point a, point b) {
    return sqrt(1.0 * (a.x - b.x) * (a.x - b.x) + 1.0 * (a.y - b.y) * (a.y - b.y));
}

double prim() {
    for (int i = 0; i <= n; ++i) d[i] = INF;
    memset(vis, 0, sizeof(vis));
    priority_queue<P, vector<P>, greater<P> > q;
    double ans = 0;
    d[1] = 0.0;
    q.push(P(0.0, 1));
    while (!q.empty()) {
        int x = q.top().second;
        q.pop();
        if (!vis[x]) {
            vis[x] = 1;
            ans += d[x];
        }
        for (int y = 1; y <= n; ++y) {
            if (!vis[y] && d[y] > g[x][y] && g[x][y] >= 10) {
                d[y] = g[x][y];
                q.push(P(d[y], y));
            }
        }
    }
    return ans;
}

int main() 
{
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) {
            scanf("%d%d", &p[i].x, &p[i].y);
        }
        memset(g, 0, sizeof(g));
        for (int i = 1; i <= n; ++i) {
            for (int j = i + 1; j <= n; ++j) {
                double len = dis(p[i], p[j]);
                if (len >= 10 && len <= 1000) {
                    g[i][j] = g[j][i] = len;
                }
            }
        }
        double ans = prim() * 100;
        if (!ans) puts("oh!");
        else printf("%.1lf\n", ans);
    }
    return 0;
}