P2045 方格取数加强版

xht · 2019-03-12 01:19:06 · 题解

题目地址：P2045 方格取数加强版

1. 点边转化：把每个格子 (i,j) 拆成一个入点一个出点。
2. 从每个入点向对应的出点连两条有向边：一条容量为 1 ，费用为格子 (i,j) 中的数；另一条容量为 k-1 ，费用为 0 。
3. 从 (i,j) 的出点到 (i,j+1) 和 (i+1,j) 的入点连有向边，容量为 k ，费用为 0 。
4. 以 (1,1) 的入点为源点， (n,n) 的出点为汇点，求最大费用最大流。

#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 6, M = 2e5 + 6;
const int inf = 0x3f3f3f3f, _inf = 0xcfcfcfcf;
int Head[N], Edge[M], Leng[M], Cost[M], Next[M], tot = 1;
int d[N], f[N], p[N];
bool v[N];
int n, k, s = 1, t, ans;

inline void add(int x, int y, int z, int c) {
    Edge[++tot] = y;
    Leng[tot] = z;
    Cost[tot] = c;
    Next[tot] = Head[x];
    Head[x] = tot;
    Edge[++tot] = x;
    Leng[tot] = 0;
    Cost[tot] = -c;
    Next[tot] = Head[y];
    Head[y] = tot;
}

inline int num(int i, int j, int k) {
    return (i - 1) * n + j + k * n * n;
}

inline bool spfa() {
    queue<int> q;
    memset(d, 0xcf, sizeof(d));
    memset(v, 0, sizeof(v));
    q.push(s);
    d[s] = 0;
    v[s] = 1;
    f[s] = inf;
    while (q.size()) {
        int x = q.front();
        v[x] = 0;
        q.pop();
        for (int i = Head[x]; i; i = Next[i]) {
            if (!Leng[i]) continue;
            int y = Edge[i];
            if (d[y] < d[x] + Cost[i]) {
                d[y] = d[x] + Cost[i];
                f[y] = min(f[x], Leng[i]);
                p[y] = i;
                if (!v[y]) {
                    q.push(y);
                    v[y] = 1;
                }
            }
        }
    }
    return d[t] != _inf;
}

void upd() {
    int x = t;
    while (x != s) {
        int i = p[x];
        Leng[i] -= f[t];
        Leng[i^1] += f[t];
        x = Edge[i^1];
    }
    ans += d[t] * f[t];
}

int main() {
    cin >> n >> k;
    t = 2 * n * n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            int c;
            scanf("%d", &c);
            add(num(i, j, 0), num(i, j, 1), 1, c);
            add(num(i, j, 0), num(i, j, 1), k - 1, 0);
            if (j < n) add(num(i, j, 1), num(i, j + 1, 0), k, 0);
            if (i < n) add(num(i, j, 1), num(i + 1, j, 0), k, 0);
        }
    while (spfa()) upd();
    cout << ans << endl;
    return 0;
}