简答题
偏难
#22123
4、交通规划
4、交通规划



答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 360005; // 增大数组容量适配题目规模
const ll INF = 1e18;
struct Edge {
int to, rev;
ll cap;
Edge(int t, int r, ll c) : to(t), rev(r), cap(c) {}
};
vector<Edge> g[MAXN];
int level[MAXN], iter[MAXN];
int n, m, T;
// 添加双向边
void add_edge(int from, int to, ll cap) {
g[from].emplace_back(to, (int)g[to].size(), cap);
g[to].emplace_back(from, (int)g[from].size() - 1, 0); // 反向边初始容量为0
}
// BFS构建层次图
void bfs(int s) {
memset(level, -1, sizeof(level));
queue<int> q;
level[s] = 0;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
for (const Edge& e : g[u]) {
if (e.cap > 0 && level[e.to] < 0) {
level[e.to] = level[u] + 1;
q.push(e.to);
}
}
}
}
// DFS寻找增广路
ll dfs(int u, int t, ll f) {
if (u == t) return f;
for (int& i = iter[u]; i < g[u].size(); ++i) {
Edge& e = g[u][i];
if (e.cap > 0 && level[u] < level[e.to]) {
ll d = dfs(e.to, t, min(f, e.cap));
if (d > 0) {
e.cap -= d;
g[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}
// 计算最大流(最小割)
ll max_flow(int s, int t) {
ll flow = 0;
while (true) {
bfs(s);
if (level[t] < 0) return flow;
memset(iter, 0, sizeof(iter));
ll f;
while ((f = dfs(s, t, INF)) > 0) {
flow += f;
}
}
}
// 射线编号转网格坐标(修正版)
pair<int, int> get_coord(int p) {
p--; // 转为0基索引
if (p < m) { // 上边界:(1, p+1)
return {0, p};
}
p -= m;
if (p < n-1) { // 右边界:(p+2, m)
return {p+1, m-1};
}
p -= n-1;
if (p < m) { // 下边界:(n, m-p)
return {n-1, m-1 - p};
}
p -= m; // 左边界:(n-p, 1)
return {n-1 - p, 0};
}
int main() {
// 移除文件操作,适配标准输入输出
scanf("%d%d%d", &n, &m, &T);
// 存储水平和垂直边的权重
vector<vector<ll>> horizontal(n-1, vector<ll>(m));
vector<vector<ll>> vertical(n, vector<ll>(m-1));
// 读取水平边(上下相邻格子)
for (int i = 0; i < n-1; ++i) {
for (int j = 0; j < m; ++j) {
scanf("%lld", &horizontal[i][j]);
}
}
// 读取垂直边(左右相邻格子)
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m-1; ++j) {
scanf("%lld", &vertical[i][j]);
}
}
while (T--) {
int k;
scanf("%d", &k);
// 清空图结构
for (int i = 0; i < MAXN; ++i) {
g[i].clear();
}
int S = 0; // 源点(黑色)
int T_node = n * m + 1; // 汇点(白色)
int node_cnt = n * m; // 网格节点总数
// 连接水平相邻格子(i,j)和(i+1,j)
for (int i = 0; i < n-1; ++i) {
for (int j = 0; j < m; ++j) {
int u = i * m + j + 1; // 网格节点编号从1开始
int v = (i+1) * m + j + 1;
ll cap = horizontal[i][j];
add_edge(u, v, cap);
add_edge(v, u, cap); // 双向边
}
}
// 连接垂直相邻格子(i,j)和(i,j+1)
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m-1; ++j) {
int u = i * m + j + 1;
int v = i * m + (j+1) + 1;
ll cap = vertical[i][j];
add_edge(u, v, cap);
add_edge(v, u, cap); // 双向边
}
}
// 处理附加点约束
for (int i = 0; i < k; ++i) {
ll x3;
int p, t;
scanf("%lld%d%d", &x3, &p, &t);
// 获取射线对应的网格坐标
auto [r, c] = get_coord(p);
if (r < 0 || r >= n || c < 0 || c >= m) {
// 无效坐标处理
continue;
}
int node = r * m + c + 1; // 转换为节点编号
if (t == 1) { // 必须染黑色(连接到源点)
add_edge(S, node, INF); // 保证不会被割开
add_edge(node, S, x3); // 附加权重
} else { // 必须染白色(连接到汇点)
add_edge(node, T_node, INF); // 保证不会被割开
add_edge(T_node, node, x3); // 附加权重
}
}
// 计算并输出最小割(最大流)
printf("%lld\n", max_flow(S, T_node));
}
return 0;
}</pre><p><br/></p>
这道题暂未补解析。