[CSP-S 2021] 交通规划

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

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

OJ: luogu

题目 ID: P7916

难度:提高+/省选-

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

日期: 2026-07-06 08:46

题意

给定一个 $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// brute.cpp：小网格暴力解，枚举每个格点染黑/白，直接计算割边代价。
#include <bits/stdc++.h>
using namespace std;

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

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

int n, m, T;
vector<BaseEdge> base_edges;

int node_id(int r, int c) {
    return (r - 1) * m + c - 1;
}

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);
}

long long 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;
    long long answer = (long long)4e18;
    for (int mask = 0; mask < (1 << total); mask++) {
        long long 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;
}

这个暴力的状态数是 $2^{n \times m}$ ，只能用于验证建模。

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

源点 S 表示黑色；
汇点 T 表示白色；
每个格点是图中的一个点；
网格内部一条权值为 w 的无向边 (u,v)，表示 u,v 颜色不同就付出 w，在网络流中建成容量为 w 的双向割边；
如果附加点颜色为黑色，且它连到格点 u、边权为 w，那么 u 被染成白色时要付出 w，所以连边 S -> u，容量为 w；
如果附加点颜色为白色，则连边 u -> T，容量为 w。

一次 S-T 割会把所有格点分到源点侧或汇点侧，正好对应黑白染色。割掉的边容量之和，正好是所有跨色边代价。因此最小割就是答案。

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

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

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

text

1dp[l][r]：把边界变化点 l..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// main.cpp：平面图最小割转对偶图最短路，再用环形区间 DP 配对颜色变化段。
#include <bits/stdc++.h>
using namespace std;

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

struct Edge {
    int to;
    int next;
    int weight;
};

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

int n, m, query_count, face_count, edge_count;
int head[MAXNODE], saved_head[MAXEDGE], saved_node[MAXEDGE], saved_count;
Edge edges[MAXEDGE];
int boundary_face[5005];
PointInfo point_info[60];
long long dist_value[MAXNODE];
bool visited_node[MAXNODE];
long long dist_between[60][60];
long long dp[120][120];
int changed_node[120];

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_count++;
    edges[edge_count].to = v;
    edges[edge_count].weight = w;
    edges[edge_count].next = head[u];
    head[u] = edge_count;
}

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_count -= saved_count;
    while (saved_count > 0) {
        head[saved_node[saved_count]] = saved_head[saved_count];
        saved_count--;
    }
}

void dijkstra(int source, int total_nodes) {
    for (int i = 0; i < total_nodes; i++) {
        dist_value[i] = INF;
        visited_node[i] = false;
    }

    priority_queue<pair<long long, int>, vector<pair<long long, int> >, greater<pair<long long, 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].next) {
            int v = edges[e].to;
            long long 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;

        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;
    }

    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]];
        }
    }

    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]];
    }

    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]);
            }
        }
    }

    long long 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);
        }
    }

    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 <= 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] 交通规划

目录

题意

思路

代码

复杂度

总结