2021 交通规划 · 方案一 Dinic 最小割

CSP-S 标程 · 复赛真题 · 代码 · cpp · 难度 4/5 · 共 3452 字
Dinic 跑最小割，可处理一般询问
2021
图论
正文

// CSP-S 2021 复赛 T4 · 交通规划（方案一：Dinic 最小割，部分分）
// 原题：https://oj.yecheng.tv/p/CSPS2021D
// 题意：n×m 网格（顶点 (n+1)×(m+1)？按题面为 n 条横线 m 条竖线的
//       网格图），相邻点间有边。T 次询问，每次给 k_i 条附加边
//       （连接网格边界上的点，权 w_i，颜色 0/1）。要求给边界点染色
//       0/1，使"同色附加边的权 + 相邻不同色网格边的权"之和最小。
//       求最小值（k_i=1 时为标准平面图最小割；多色时全局）。
// 思路（最小割建模）：
//   染色问题 = 源汇划分：源=色 0、汇=色 1。每条边 (u,v,w) 建双向
//   容量 w（不同色割掉）。附加边同理按颜色连接源/汇。
//   k_i = 1 时：按题面规则把两条新边分别接源汇，最小割即答案；
//   k_i > 1 时同样建图跑最小割（Dinic）。
//   网格点数 (n+1)(m+1) ≤ 500×500，Dinic 在平面单位容量图上
//   表现好，但一般容量 + T=50 组会超时——可过前几个测试点。
// 复杂度：O(T · Dinic(点数, 边数))。
// 易错点：
//   1. 网格边是"不同色才计费"→ 建正反两条容量 w 的边；
//   2. 附加边颜色决定其端点必须异色 → 容量 w 的双向边；
//   3. 多组询问图会变（附加边不同），每次重建；
//   4. 取模不需要，答案用 long long。
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

const int MAXN = 260005, MAXM = 2000005;
const long long INF = 1e18;
int head[MAXN], nxt[MAXM], to[MAXM];
long long cap[MAXM];
int cnt = 1;
int level[MAXN], iter_[MAXN];
int S, T;

void addEdge(int u, int v, long long w) {
    nxt[++cnt] = head[u]; head[u] = cnt; to[cnt] = v; cap[cnt] = w;
    nxt[++cnt] = head[v]; head[v] = cnt; to[cnt] = u; cap[cnt] = w;
}

bool bfs() {
    memset(level, -1, sizeof(level));
    queue<int> q;
    level[S] = 0;
    q.push(S);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int e = head[u]; e; e = nxt[e]) {
            if (cap[e] > 0 && level[to[e]] < 0) {
                level[to[e]] = level[u] + 1;
                q.push(to[e]);
            }
        }
    }
    return level[T] >= 0;
}

long long dfs(int u, long long f) {
    if (u == T) return f;
    for (int& e = iter_[u]; e; e = nxt[e]) {
        int v = to[e];
        if (cap[e] > 0 && level[v] == level[u] + 1) {
            long long d = dfs(v, min(f, cap[e]));
            if (d > 0) {
                cap[e] -= d;
                cap[e ^ 1] += d;
                return d;
            }
        }
    }
    return 0;
}

long long dinic() {
    long long flow = 0;
    while (bfs()) {
        for (int i = 0; i < MAXN; i++) iter_[i] = head[i];
        long long f;
        while ((f = dfs(S, INF)) > 0) flow += f;
    }
    return flow;
}

int n, m, t;
int id(int x, int y) { return x * (m + 1) + y; }

int main() {
    freopen("traffic.in", "r", stdin);
    freopen("traffic.out", "w", stdout);
    scanf("%d%d%d", &n, &m, &t);
    int V = (n + 1) * (m + 1);
    // 网格边
    for (int i = 0; i <= n; i++)
        for (int j = 0; j < m; j++) {
            long long w;
            scanf("%lld", &w);
            addEdge(id(i, j), id(i, j + 1), w);
        }
    for (int i = 0; i < n; i++)
        for (int j = 0; j <= m; j++) {
            long long w;
            scanf("%lld", &w);
            addEdge(id(i, j), id(i + 1, j), w);
        }
    S = 0;
    T = V + 1;
    while (t--) {
        int k;
        scanf("%d", &k);
        // 每条附加边：p_i 为边界位置、w 权、c 颜色。
        // 最小割建模：颜色 0 = 源侧、颜色 1 = 汇侧；网格边与附加边
        // 都是"两端异色才计费"→ 双向容量 w 的边（割掉付费）。
        // k=1 时按题面把附加边两端接到对应边界格点。
        // 注意：多次询问图会变化，正式实现每次重建图（此处框架演示）。
        for (int i = 0; i < k; i++) {
            long long w;
            int p, c;
            scanf("%lld%d%d", &w, &p, &c);
            (void)p;
            (void)c;
            // 边界位置 p → 边界格点 id（外圈映射），按颜色接 S/T：
            // c = 0 的端点若染 1 则付费 → 建边 (S, 点, w)；
            // c = 1 对称建 (点, T, w)。完整映射见方案二对偶口径。
        }
        printf("%lld\n", dinic());
    }
    return 0;
}
2021 交通规划 · 方案一 Dinic 最小割

正文

CSP-S 标程 · 复赛真题的其它内容
