[USACO3.1] 最短网络 Agri-Net

题意

给出 n 个农场之间两两连线的代价矩阵，要求选出一种连线方案：

能让所有农场都连通
总花费最小

这就是一张无向带权图上的最小生成树问题。

思路

先看一个最直接的小数据暴力：

cpp

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// brute.cpp：按定义枚举所有可能的生成树，只适合很小的数据。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10;
const int MAXM = 50;
const int INF = 1e9;

struct Edge {
    int u, v, w;
} edges[MAXM];

int n;
int edge_cnt;
int picked[MAXM];
int best_answer = INF;

int fa[MAXN];

void init_dsu() {
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
}

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

void unite(int x, int y) {
    x = find_root(x);
    y = find_root(y);
    if (x != y) {
        fa[x] = y;
    }
}

bool check_tree(int picked_cnt) {
    if (picked_cnt != n - 1) {
        return false;
    }

    init_dsu();
    for (int i = 1; i <= picked_cnt; i++) {
        int id = picked[i];
        unite(edges[id].u, edges[id].v);
    }

    int root = find_root(1);
    for (int i = 2; i <= n; i++) {
        if (find_root(i) != root) {
            return false;
        }
    }
    return true;
}

void dfs(int pos, int picked_cnt, int sum) {
    if (picked_cnt > n - 1) {
        return;
    }
    if (sum >= best_answer) {
        return;
    }
    if (pos > edge_cnt) {
        if (check_tree(picked_cnt)) {
            best_answer = min(best_answer, sum);
        }
        return;
    }

    picked[picked_cnt + 1] = pos;
    dfs(pos + 1, picked_cnt + 1, sum + edges[pos].w);
    dfs(pos + 1, picked_cnt, sum);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    edge_cnt = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int w;
            cin >> w;
            if (j > i) {
                edges[++edge_cnt] = {i, j, w};
            }
        }
    }

    dfs(1, 0, 0);
    cout << best_answer << '\n';

    return 0;
}

暴力按最小生成树的定义做：

从所有边里选出 n-1 条
判断这 n-1 条边能不能把所有点连起来
在所有合法生成树里取边权和最小的那个

这个方法非常直观，但边一多就完全不可用。

题目输入给的是完整邻接矩阵，图非常稠密，直接用 Prim 会比 Kruskal 更顺手。

Prim 的想法是：

先任选一个点放进生成树
对每个还没加入生成树的点，维护它和当前生成树之间的最小连边代价
每次选其中代价最小的点加入生成树
用这个新点去更新其它点的最小连边代价

为什么这样是对的？

因为每一步都在“已选点集合”和“未选点集合”之间，选了一条最便宜的跨边。根据最小生成树的切分性质，这样的边一定可以放心加入答案。

代码

cpp

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;
const int INF = 1e9;

int n;
int cost[MAXN][MAXN];
int dist_to_tree[MAXN];
bool vis[MAXN];

int prim() {
    for (int i = 1; i <= n; i++) {
        dist_to_tree[i] = INF;
        vis[i] = false;
    }

    dist_to_tree[1] = 0;
    int answer = 0;

    for (int i = 1; i <= n; i++) {
        int u = 0;

        for (int j = 1; j <= n; j++) {
            if (vis[j]) {
                continue;
            }
            if (u == 0 || dist_to_tree[j] < dist_to_tree[u]) {
                u = j;
            }
        }

        vis[u] = true;
        answer += dist_to_tree[u];

        for (int v = 1; v <= n; v++) {
            if (vis[v]) {
                continue;
            }
            if (cost[u][v] < dist_to_tree[v]) {
                dist_to_tree[v] = cost[u][v];
            }
        }
    }

    return answer;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> cost[i][j];
        }
    }

    cout << prim() << '\n';

    return 0;
}

复杂度

设点数为 n。

邻接矩阵版 Prim 每次找一个新点，并顺手更新一整行代价：

时间复杂度 $O(n^2)$
空间复杂度 $O(n^2)$

总结

这题的本质就是最小生成树。因为输入天然就是矩阵，直接写 Prim 最自然：维护“每个点离当前生成树最近的代价”，一轮一轮扩展即可。

[USACO3.1] 最短网络 Agri-Net

目录

题意

思路

代码

复杂度

总结