[USACO04DEC] Cow Ski Area G

题意

给一个 L x W 的高度网格。

奶牛可以在相邻格子之间滑雪，但只能从高处滑到低处，或者在同高度之间移动，不能从低处滑到高处。

现在可以额外修一些双向缆车：

一条缆车可以连接任意两个格子
缆车是双向的

要求修最少多少条缆车，才能让任意两个格子都互相到达。

把题面翻译成图论就是：

每个格子是一个点
能滑过去就连一条有向边
缆车相当于补一条双向边
最终希望整张有向图强连通

小表格

先看一个小例子：

2	2	1
2	3	1

这个网格里：

高度为 2 的三个格子彼此能双向到达，是一个强连通块
高度为 1 的两个格子也是一个强连通块
高度为 3 的格子单独是一个块

所以这题真正要处理的不是单个格子，而是这些“同高且连通”的整块。

思路

先看一个更直接的小数据版：

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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138// brute.cpp：直接把每个格子看成有向图里的一个点，再做强连通分量。
// 这版更接近题目的原始图模型，适合帮助理解和小数据对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXR = 35;
const int MAXC = 35;

int w, l;
int h[MAXR][MAXC];

vector<int> g[1005], rg[1005];
bool vis[1005];
int scc_id[1005];
vector<int> order;

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

bool in_board(int x, int y) {
    return x >= 1 && x <= l && y >= 1 && y <= w;
}

int id(int x, int y) {
    return (x - 1) * w + y;
}

void dfs1(int u) {
    vis[u] = true;
    for (size_t i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (!vis[v]) {
            dfs1(v);
        }
    }
    order.push_back(u);
}

void dfs2(int u, int color) {
    scc_id[u] = color;
    for (size_t i = 0; i < rg[u].size(); i++) {
        int v = rg[u][i];
        if (scc_id[v] == 0) {
            dfs2(v, color);
        }
    }
}

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

    cin >> w >> l;
    for (int i = 1; i <= l; i++) {
        for (int j = 1; j <= w; j++) {
            cin >> h[i][j];
        }
    }

    int tot = w * l;
    for (int i = 1; i <= tot; i++) {
        g[i].clear();
        rg[i].clear();
        vis[i] = false;
        scc_id[i] = 0;
    }
    order.clear();

    for (int i = 1; i <= l; i++) {
        for (int j = 1; j <= w; j++) {
            int u = id(i, j);
            for (int k = 0; k < 4; k++) {
                int ni = i + dx[k];
                int nj = j + dy[k];
                if (!in_board(ni, nj)) {
                    continue;
                }

                if (h[ni][nj] <= h[i][j]) {
                    int v = id(ni, nj);
                    g[u].push_back(v);
                    rg[v].push_back(u);
                }
            }
        }
    }

    for (int i = 1; i <= tot; i++) {
        if (!vis[i]) {
            dfs1(i);
        }
    }

    int scc_cnt = 0;
    for (int i = (int)order.size() - 1; i >= 0; i--) {
        int u = order[i];
        if (scc_id[u] == 0) {
            scc_cnt++;
            dfs2(u, scc_cnt);
        }
    }

    if (scc_cnt == 1) {
        cout << 0 << '\n';
        return 0;
    }

    vector<int> indeg(scc_cnt + 1, 0);
    vector<int> outdeg(scc_cnt + 1, 0);

    for (int u = 1; u <= tot; u++) {
        for (size_t i = 0; i < g[u].size(); i++) {
            int v = g[u][i];
            int su = scc_id[u];
            int sv = scc_id[v];
            if (su != sv) {
                outdeg[su] = 1;
                indeg[sv] = 1;
            }
        }
    }

    int source_cnt = 0;
    int sink_cnt = 0;

    for (int i = 1; i <= scc_cnt; i++) {
        if (indeg[i] == 0) {
            source_cnt++;
        }
        if (outdeg[i] == 0) {
            sink_cnt++;
        }
    }

    cout << max(source_cnt, sink_cnt) << '\n';

    return 0;
}

brute.cpp 是最原始的图论建模：

每个格子建成一个点
能滑过去就连一条有向边
先求整张图的强连通分量
再缩点统计答案

这个写法最贴近题面，但正式做法还能再往前走一步。

关键观察是：

如果两个格子能互相到达，那么它们的高度一定相同

原因很直接：

一条合法路径上的高度只能不升
如果 A 能到 B，B 也能回到 A，那沿着来回两条路径，高度既不能升也不能降，最后只能处处相等

于是可以得到一个更强的结论：

一个强连通分量，恰好就是“同高且四联通”的一整块格子

这样就没必要真的在 25 万个格子上跑通用 SCC 了。我们只要：

先 BFS 把每块“同高连通块”染成一个编号
把这些块看成点
若相邻两格属于不同块，且高度从高到低，就在块之间连一条有向边

缩点后的图一定是 DAG，因为边只会从高处指向低处，不可能绕一圈回到原高度。

最后就变成经典结论：

如果缩点后只有一个点，答案是 0
否则答案是 max(入度为 0 的点数, 出度为 0 的点数)

为什么？

每个入度为 0 的块，必须靠缆车给它补一条“进入它”的路
每个出度为 0 的块，必须靠缆车给它补一条“离开它”的路
一条双向缆车最多同时解决一个源点和一个汇点

因此答案至少是这两者的较大值。
而这个下界也是能达到的，这是缩点 DAG 变强连通的标准结论。

代码

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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127#include <bits/stdc++.h>
using namespace std;

const int MAXR = 505;
const int MAXC = 505;
const int MAXV = 250000 + 5;

int w, l;
int h[MAXR][MAXC];
int comp_id[MAXR][MAXC];

int qx[MAXV], qy[MAXV];
int indeg[MAXV], outdeg[MAXV];
int comp_cnt;

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

bool in_board(int x, int y) {
    return x >= 1 && x <= l && y >= 1 && y <= w;
}

// 同高且四联通的格子可以互相滑到，所以它们本身就是一个强连通块。
void bfs_component(int sx, int sy) {
    int front = 0;
    int back = 0;

    qx[back] = sx;
    qy[back] = sy;
    back++;

    comp_cnt++;
    comp_id[sx][sy] = comp_cnt;

    while (front < back) {
        int x = qx[front];
        int y = qy[front];
        front++;

        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];

            if (!in_board(nx, ny)) {
                continue;
            }
            if (comp_id[nx][ny] != 0) {
                continue;
            }
            if (h[nx][ny] != h[x][y]) {
                continue;
            }

            comp_id[nx][ny] = comp_cnt;
            qx[back] = nx;
            qy[back] = ny;
            back++;
        }
    }
}

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

    cin >> w >> l;
    for (int i = 1; i <= l; i++) {
        for (int j = 1; j <= w; j++) {
            cin >> h[i][j];
        }
    }

    for (int i = 1; i <= l; i++) {
        for (int j = 1; j <= w; j++) {
            if (comp_id[i][j] == 0) {
                bfs_component(i, j);
            }
        }
    }

    if (comp_cnt == 1) {
        cout << 0 << '\n';
        return 0;
    }

    // 缩点后只关心每个点是否有入边/出边，不需要去重后的完整边集。
    for (int i = 1; i <= l; i++) {
        for (int j = 1; j <= w; j++) {
            for (int k = 0; k < 4; k++) {
                int ni = i + dx[k];
                int nj = j + dy[k];

                if (!in_board(ni, nj)) {
                    continue;
                }

                int cu = comp_id[i][j];
                int cv = comp_id[ni][nj];

                if (cu == cv) {
                    continue;
                }

                if (h[i][j] > h[ni][nj]) {
                    outdeg[cu] = 1;
                    indeg[cv] = 1;
                }
            }
        }
    }

    int source_cnt = 0;
    int sink_cnt = 0;

    for (int i = 1; i <= comp_cnt; i++) {
        if (indeg[i] == 0) {
            source_cnt++;
        }
        if (outdeg[i] == 0) {
            sink_cnt++;
        }
    }

    cout << max(source_cnt, sink_cnt) << '\n';

    return 0;
}

复杂度

设格子总数为 N = L * W。

每个格子只会被 BFS 染色一次，之后再枚举常数个相邻方向，所以：

时间复杂度 $O(N)$
空间复杂度 $O(N)$

总结

这题最重要的不是 SCC 模板本身，而是先看出：

强连通块其实就是同高连通块

一旦把这个观察抓住，题目就从“网格有向图最少加边”变成了：

同高块缩点
得到一张从高到低的 DAG
统计源点数和汇点数

最后直接套 max(源点数, 汇点数) 即可。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

[USACO04DEC] Cow Ski Area G

目录

题意

小表格

思路

代码

复杂度

总结

一图流解析