[CSP-S 2021] 交通规划

GitHub跳转原题关系图返回列表

把平面图最小割转成对偶图最短路，再对边界颜色变化点做环形区间 DP。

OJ: luogu

题目 ID: P7916

难度:提高+/省选-

标签:图论最小割对偶图最短路动态规划

创建: 2026-07-06 08:46

更新: 2026-10-07 10:45

形式化题目

给定 $n \times m$ 的格点网格，相邻格点间有非负边权。进行 $T$ 次询问，每次在网格边界外添加 $k$ 个已知颜色的附加点，每个附加点通过一条有权边连到最近的格点。

要求将网格内所有格点染成黑色或白色，使得两端颜色不同的边的边权和最小。

暴力解法

思路

小网格下直接枚举每个格点的颜色（ $2^{n \times m}$ 种），计算所有跨色边的代价之和。

代码

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-06 08:46
 * update_at: 2026-10-01 21:03
 */
// brute.cpp：小网格暴力解，枚举每个格点染黑/白，直接计算割边代价。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct BaseEdge {
    int u;
    int v;
    int w;
};

struct ExtraEdge {
    int u;
    int w;
    int color;
};

int n, m, T;
vector<BaseEdge> base_edges; // 网格内部的所有边

// 格点 (r,c) 的编号，从 0 开始
int node_id(int r, int c) {
    return (r - 1) * m + c - 1;
}

// 边界射线 p 对应的最近格点编号
// 边界顺序：上侧(1..m) -> 右侧(m+1..m+n) -> 下侧(m+n+1..m+2n) -> 左侧(m+2n+1..2m+2n)
int boundary_node(int p) {
    if (p <= m) {
        return node_id(1, p);           // 上侧
    }
    p -= m;
    if (p <= n) {
        return node_id(p, m);           // 右侧
    }
    p -= n;
    if (p <= m) {
        return node_id(n, m - p + 1);   // 下侧（逆序）
    }
    p -= m;
    return node_id(n - p + 1, 1);       // 左侧（逆序）
}

// 处理一次询问：枚举所有染色方案，计算最小跨色边代价
ll solve_query() {
    int k;
    cin >> k;
    vector<ExtraEdge> extra_edges;
    for (int i = 1; i <= k; i++) {
        int x, p, color;
        cin >> x >> p >> color;
        ExtraEdge e;
        e.u = boundary_node(p);
        e.w = x;
        e.color = color;
        extra_edges.push_back(e);
    }

    int total = n * m;
    ll answer = (ll)4e18;
    for (int mask = 0; mask < (1 << total); mask++) {
        ll cost = 0;
        // 网格内部边的跨色代价
        for (int i = 0; i < (int)base_edges.size(); i++) {
            int cu = (mask >> base_edges[i].u) & 1;
            int cv = (mask >> base_edges[i].v) & 1;
            if (cu != cv) {
                cost += base_edges[i].w;
            }
        }
        // 附加点到格点的跨色代价
        for (int i = 0; i < (int)extra_edges.size(); i++) {
            int cu = (mask >> extra_edges[i].u) & 1;
            if (cu != extra_edges[i].color) {
                cost += extra_edges[i].w;
            }
        }
        answer = min(answer, cost);
    }
    return answer;
}

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

    cin >> n >> m >> T;

    // 读入水平边（相邻行之间）
    for (int r = 1; r < n; r++) {
        for (int c = 1; c <= m; c++) {
            int w;
            cin >> w;
            BaseEdge e;
            e.u = node_id(r, c);
            e.v = node_id(r + 1, c);
            e.w = w;
            base_edges.push_back(e);
        }
    }

    // 读入垂直边（相邻列之间）
    for (int r = 1; r <= n; r++) {
        for (int c = 1; c < m; c++) {
            int w;
            cin >> w;
            BaseEdge e;
            e.u = node_id(r, c);
            e.v = node_id(r, c + 1);
            e.w = w;
            base_edges.push_back(e);
        }
    }

    while (T--) {
        cout << solve_query() << '\n';
    }

    return 0;
}

复杂度

时间： $O(2^{nm} \cdot (nm + k))$
空间： $O(nm)$

瓶颈

状态数指数增长，只能处理 $n, m \leqslant 3$ 左右的极小网格。

正解

思路

这类"每个点二选一，边在两端选择不同时产生代价"的问题，可以看成源汇最小割模型：

源点 $S$ 表示黑色，汇点 $T$ 表示白色；
每个格点是图中的一个点；
网格内部一条权值为 $w$ 的无向边 $(u,v)$ ，建成容量为 $w$ 的双向割边；
黑色附加点连到格点 $u$ 、边权为 $w$ ，则连边 $S \to u$ ，容量为 $w$ （ $u$ 染白色时割断）；
白色附加点连边 $u \to T$ ，容量为 $w$ （ $u$ 染黑色时割断）。

一次 $S$ - $T$ 割正好对应一种黑白染色，割掉的边容量之和就是所有跨色边代价。因此最小割就是答案。

但直接跑最大流太慢。网格是平面图，平面图中的最小割可以转成对偶图上的最短路：原图里割掉一条边，对偶图中就相当于走过这条边对应的对偶边。

对于一次询问，把所有附加点按边界射线编号排成环。相邻两个附加点之间的一段边界属于同一个"外部区域"，代码为每段边界建立一个对偶点，并用权值为附加边权的边连接相邻外部区域。

如果相邻两个附加点颜色不同，那么这两个外部区域之间必须被某条割线分开。于是只关心所有"颜色发生变化的位置"。这些位置在边界上成环出现，割线之间不能交叉，所以可以用环形区间 DP 配对它们：

$dp[l][r]$ ：把边界变化点 $l \dots r$ 这段全部配对的最小代价。

转移有两类：

$l$ 和 $r$ 配成一对，中间继续配对；
把区间拆成两段分别配对。

任意两个变化点之间的配对代价，就是对偶图上这两个外部区域之间的最短路。代码对每个变化点跑一次 Dijkstra，得到这些代价。

代码

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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-06 08:46
 * update_at: 2026-10-01 21:03
 */
// main.cpp：平面图最小割转对偶图最短路，再用环形区间 DP 配对颜色变化段。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXNODE = 260000;
const int MAXEDGE = 1300000;
const ll INF = (ll)4e18;

struct Edge {
    int to;
    int nxt; // 下一条边的编号，避开 std::next
    int weight;
};

struct PointInfo {
    int weight;
    int position;
    int color;
};

int n, m, query_count, face_count, edge_cnt;

// 对偶图链式前向星
int head[MAXNODE];
Edge edges[MAXEDGE];

// 临时边回滚机制：每次询问在对偶图上添加临时边，询问结束后回滚
int saved_head[MAXEDGE];
int saved_node[MAXEDGE];
int saved_count;

// boundary_face[p]：边界射线 p 对应的外部 face 编号
int boundary_face[5005];

// 每次询问的附加点信息
PointInfo point_info[60];

// Dijkstra 距离数组和访问标记
ll dist_value[MAXNODE];
bool visited_node[MAXNODE];

// dist_between[i][j]：第 i 个和第 j 个颜色变化点之间的最短路
ll dist_between[60][60];

// dp[i][j]：环形区间 DP，变化点 i 到 j 全部配对的最小代价
ll dp[120][120];

// changed_node[i]：环形展开后的变化点编号
int changed_node[120];

// 格点 (x,y) 对应的 face 编号（对偶图中的节点）
int face_id(int x, int y) {
    return x * (m + 1) + y;
}

// 按位置排序附加点
bool cmp_point(const PointInfo &a, const PointInfo &b) {
    return a.position < b.position;
}

// 链式前向星加一条有向边
void add_directed_edge(int u, int v, int w) {
    edge_cnt++;
    edges[edge_cnt].to = v;
    edges[edge_cnt].weight = w;
    edges[edge_cnt].nxt = head[u];
    head[u] = edge_cnt;
}

// 加一条无向边（两条有向边）
void add_base_edge(int u, int v, int w) {
    add_directed_edge(u, v, w);
    add_directed_edge(v, u, w);
}

// 添加临时边（用于当前询问），同时记录回滚信息
void add_temp_edge(int u, int v, int w) {
    saved_count++;
    saved_head[saved_count] = head[u];
    saved_node[saved_count] = u;
    add_directed_edge(u, v, w);
}

// 回滚本次询问添加的所有临时边
void reset_temp_edges() {
    edge_cnt -= saved_count;
    while (saved_count > 0) {
        head[saved_node[saved_count]] = saved_head[saved_count];
        saved_count--;
    }
}

// Dijkstra 最短路：从 source 到所有节点的最短距离
void dijkstra(int source, int total_nodes) {
    for (int i = 0; i < total_nodes; i++) {
        dist_value[i] = INF;
        visited_node[i] = false;
    }

    // 小根堆：pair<距离, 节点>
    priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > heap;
    dist_value[source] = 0;
    heap.push(make_pair(0, source));

    while (!heap.empty()) {
        int u = heap.top().second;
        heap.pop();
        if (visited_node[u]) {
            continue;
        }
        visited_node[u] = true;

        for (int e = head[u]; e != 0; e = edges[e].nxt) {
            int v = edges[e].to;
            ll nd = dist_value[u] + edges[e].weight;
            if (nd < dist_value[v]) {
                dist_value[v] = nd;
                heap.push(make_pair(nd, v));
            }
        }
    }
}

// 处理一次询问
void solve_query() {
    int k;
    cin >> k;
    for (int i = 1; i <= k; i++) {
        cin >> point_info[i].weight >> point_info[i].position >> point_info[i].color;
    }
    sort(point_info + 1, point_info + k + 1, cmp_point);
    point_info[k + 1] = point_info[1];

    int perimeter = 2 * n + 2 * m;
    vector<int> boundary_blocks;

    // 为每段边界建立临时节点，并连接相邻边界段
    for (int i = 1; i <= k; i++) {
        int block_node = face_count + i - 1;

        // 将第 i 个附加点对应的外部区域与边界上该段的所有 face 相连
        for (int p = point_info[i].position; p != point_info[i + 1].position; p = p % perimeter + 1) {
            add_temp_edge(block_node, boundary_face[p], 0);
            add_temp_edge(boundary_face[p], block_node, 0);
        }

        // 相邻两个外部区域之间用附加边权连接
        int next_block = (i == k) ? face_count : block_node + 1;
        int connect_weight = (i == k) ? point_info[1].weight : point_info[i + 1].weight;
        add_temp_edge(block_node, next_block, connect_weight);
        add_temp_edge(next_block, block_node, connect_weight);

        // 记录颜色变化的位置
        if (point_info[i].color != point_info[i + 1].color) {
            boundary_blocks.push_back(block_node);
        }
    }

    int change_count = (int)boundary_blocks.size();
    if (change_count < 2) {
        cout << 0 << '\n';
        reset_temp_edges();
        return;
    }

    // 对每个颜色变化点跑 Dijkstra，得到两两之间的最短路
    int total_nodes = face_count + k;
    for (int i = 0; i < change_count; i++) {
        dijkstra(boundary_blocks[i], total_nodes);
        for (int j = 0; j < change_count; j++) {
            dist_between[i][j] = dist_value[boundary_blocks[j]];
        }
    }

    // 环形展开：将变化点环复制一倍，方便做环形区间 DP
    for (int i = 0; i < change_count; i++) {
        changed_node[i] = i;
        changed_node[i + change_count] = i;
    }

    for (int i = 0; i < change_count * 2; i++) {
        for (int j = 0; j < change_count * 2; j++) {
            dp[i][j] = INF;
        }
    }

    // 相邻两个变化点直接配对
    for (int i = 0; i + 1 < change_count * 2; i++) {
        dp[i][i + 1] = dist_between[changed_node[i]][changed_node[i + 1]];
    }

    // 区间 DP：枚举区间长度，计算 dp[l][r]
    for (int len = 4; len <= change_count; len += 2) {
        for (int l = 0; l + len - 1 < change_count * 2; l++) {
            int r = l + len - 1;
            dp[l][r] = dp[l + 1][r - 1] + dist_between[changed_node[l]][changed_node[r]];
            for (int mid = l + 1; mid <= r - 2; mid += 2) {
                dp[l][r] = min(dp[l][r], dp[l][mid] + dp[mid + 1][r]);
            }
        }
    }

    // 在环形展开的所有起点中取最小值
    ll answer = INF;
    for (int start = 0; start < change_count; start++) {
        answer = min(answer, dp[start][start + change_count - 1]);
    }
    cout << answer << '\n';

    reset_temp_edges();
}

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

    cin >> n >> m >> query_count;
    face_count = (n + 1) * (m + 1);

    // 读入水平边（相邻行之间的边）
    for (int r = 1; r < n; r++) {
        for (int c = 1; c <= m; c++) {
            int w;
            cin >> w;
            add_base_edge(face_id(r, c - 1), face_id(r, c), w);
        }
    }

    // 读入垂直边（相邻列之间的边）
    for (int r = 1; r <= n; r++) {
        for (int c = 1; c < m; c++) {
            int w;
            cin >> w;
            add_base_edge(face_id(r - 1, c), face_id(r, c), w);
        }
    }

    // 建立边界射线到外部 face 的映射
    for (int i = 1; i <= m; i++) {
        boundary_face[i] = face_id(0, i);
    }
    for (int i = m + 1; i <= n + m; i++) {
        boundary_face[i] = face_id(i - m, m);
    }
    for (int i = n + m + 1; i <= n + 2 * m; i++) {
        boundary_face[i] = face_id(n, n + 2 * m - i);
    }
    for (int i = n + 2 * m + 1; i <= 2 * n + 2 * m; i++) {
        boundary_face[i] = face_id(2 * n + 2 * m - i, 0);
    }

    while (query_count--) {
        solve_query();
    }

    return 0;
}

复杂度

设对偶图点数、边数都是 $O(nm)$ 。一次询问中颜色变化点数量不超过 $k \leqslant 50$ 。

每个变化点跑一次 Dijkstra： $O(k \cdot nm \log(nm))$
区间 DP： $O(k^3)$

所有询问的 $k$ 总和不超过 $50$ ，整体可以通过。

总结

本题的关键是两次转化：

染黑/染白对应源汇两侧，跨色边代价对应最小割；
网格是平面图，最小割可以在对偶图上变成最短路。

最后利用边界颜色变化点数量很小，把多条割线的不交叉配对交给区间 DP 处理。

P7916 [CSP-S 2021] 交通规划

题目描述

给定一个平面上 $n$ 条水平直线和 $m$ 条垂直直线，它们相交形成 $n$ 行 $m$ 列的网格，从上到下第 $r$ 条水平直线和从左到右第 $c$ 条垂直直线之间的交点称为格点 $(r, c)$ 。网格中任意两个水平或垂直相邻的格点之间的线段称为一条边，每条边有一个非负整数边权。

进行 $T$ 次询问，每次询问形式如下：

给出 $k$ （ $T$ 次询问的 $k$ 可能不同）个附加点，每个附加点位于一条从网格边缘向外出发的射线上。所有从网格边缘向外出发的射线按左上-右上-右下-左下-左上的顺序依次编号为 $1$ 到 $2 n + 2 m$ ，如下图：

对于每次询问，不同附加点所在的射线互不相同。每个附加点和最近的格点之间的线段也称为一条边，也有非负整数边权（注意，在角上的格点有可能和两个附加点同时相连）。

给定每个附加点的颜色（黑色或者白色），请你将网格内每个格点的颜色染成黑白二者之一，并使得所有两端颜色不同的边的边权和最小。请输出这个最小的边权和。

输入格式

第一行，三个正整数 $n, m, T$ ，分别表示水平、垂直直线的数量，以及询问次数。

接下来 $n - 1$ 行，每行 $m$ 个非负整数。其中第 $i$ 行的第 $j$ 个非负整数 ${x 1}_{i, j}$ 表示 $(i, j)$ 和 $(i + 1, j)$ 间的边权。

接下来 $n$ 行，每行 $m - 1$ 个非负整数。其中第 $i$ 行的第 $j$ 个非负整数 ${x 2}_{i, j}$ 表示 $(i, j)$ 和 $(i, j + 1)$ 间的边权。

接下来依次输入 $T$ 组询问。第 $i$ 组询问开头为一行一个正整数 $k_i$ 表示这次询问附加点的总数。接下来 $k_i$ 行每行三个非负整数。其中第 $j$ 行依次为 ${x 3}_{i, j}, p_{i, j}, t_{i, j}$ 表示第 $j$ 个附加点和相邻格点之间的边权、所在的射线编号以及附加点颜色（ $0$ 为白色， $1$ 为黑色）。保证同一组询问内 $p_{i, j}$ 互不相同。

每行的多个整数由空格分隔。

输出格式

输出 $T$ 行，第 $i$ 行输出一个非负整数，表示第 $i$ 次询问染色之后两端颜色不同的边权和的最小值。

输入输出样例 #1

输入 #1

text

输出 #1

text

输入输出样例 #2

输入 #2

text

1见附件中的 traffic/traffic2.in

输出 #2

text

1见附件中的 traffic/traffic2.ans

输入输出样例 #3

输入 #3

text

1见附件中的 traffic/traffic3.in

输出 #3

text

1见附件中的 traffic/traffic3.ans

输入输出样例 #4

输入 #4

text

1见附件中的 traffic/traffic4.in

输出 #4

text

1见附件中的 traffic/traffic4.ans

输入输出样例 #5

输入 #5

text

1见附件中的 traffic/traffic5.in

输出 #5

text

1见附件中的 traffic/traffic5.ans

说明/提示

【样例解释 #1】

最优方案： $(1, 3), (1, 2), (2, 3)$ 为黑色； $(1, 1), (2, 1), (2, 2)$ 为白色。

【数据范围】

测试点编号	$n, m \le$	$k_i \le$
$1 \sim 2$	$5$	$50$
$3 \sim 5$	$18$	$2$
$6 \sim 8$	$18$	$50$
$9 \sim 10$	$100$	$2$
$11 \sim 12$	$100$	$50$
$13 \sim 16$	$500$	$2$
$17 \sim 20$	$500$	$50$

对于所有数据， $2 \le n, m \le 500$ ， $1 \le T \le 50$ ， $1 \le k_i \le \min \{ 2 (n + m), 50 \}$ ， $1 \le \sum_{i = 1}^{T} k_i \le 50$ ， $0 \le x \le {10}^6$ ， $1 \le p \le 2 (n + m)$ ， $t \in \{ 0, 1 \}$ 。

保证对于每个 $i \in [1, T]$ ， $p_{i, j}$ 互不相同。

【感谢 hack 数据提供】
@_Enthalpy。

[CSP-S 2021] 交通规划

目录

形式化题目

暴力解法

思路

代码

复杂度

瓶颈

正解

思路

代码

复杂度

总结