「题解」洛谷 P1935 [国家集训队]圈地计划

· · 题解

还是那个经典trick：最大价值=总价值-最小花费

每个位置都是二选一，考虑一个鱼刺型建图。

然后就是需要描述一个，如果 x 选了第 p 种方案，那么如果它的邻点也选了第 p 种方案，就有 -C 的代价，也就是有一条 -C 流量的边需要割掉。

但是如果直接 S 连向每个格子的边流量为 A，每个格子流向 T 的格子流量为 B，你会发现这个限制描述不了。

注意到网格图四联通实际上是个二分图，按照格子的横纵坐标和的奇偶性分类就是个二分图。

那么将横纵坐标和为偶数的格子，连边变成 (S,x,B),(x,T,A)，然后限制的话直接在邻点之间连 (x,y,C_x+C_y),(y,x,C_x+C_y) 流量的边，这样如果 x 和其邻点 y 如果选择了同样的一种方案，那么就需要付出 C_x+C_y 的代价。

这样用总价值减去最小割就可以了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#define pb emplace_back
#define mp std::make_pair
#define fi first
#define se second
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef std::pair<int, int> pii;
typedef std::vector<int> vi;
const ll mod = 998244353;
ll Add(ll x, ll y) { return (x+y>=mod) ? (x+y-mod) : (x+y); }
ll Mul(ll x, ll y) { return x * y % mod; }
ll Mod(ll x) { return x < 0 ? (x + mod) : (x >= mod ? (x-mod) : x); }
ll cadd(ll &x, ll y) { return x = (x+y>=mod) ? (x+y-mod) : (x+y); }
ll cmul(ll &x, ll y) { return x = x * y % mod; }
template <typename T> T Max(T x, T y) { return x > y ? x : y; }
template<typename T, typename... T2> T Max(T x, T2 ...y) { return Max(x, y...); }
template <typename T> T Min(T x, T y) { return x < y ? x : y; }
template<typename T, typename... T2> T Min(T x, T2 ...y) { return Min(x, y...); }
template <typename T> T cmax(T &x, T y) { return x = x > y ? x : y; }
template <typename T> T cmin(T &x, T y) { return x = x < y ? x : y; }
template <typename T>
T &read(T &r) {
    r = 0; bool w = 0; char ch = getchar();
    while(ch < '0' || ch > '9') w = ch == '-' ? 1 : 0, ch = getchar();
    while(ch >= '0' && ch <= '9') r = r * 10 + (ch ^ 48), ch = getchar();
    return r = w ? -r : r;
}
template<typename T1, typename... T2>
void read(T1 &x, T2& ...y) { read(x); read(y...); }
const int N = 5010;
const int M = 10010;
const ll INF = 0x7fffffffffffffff;
int n, m, A[110][110], B[110][110], C[110][110], p[110][110];
int tot, S, T, ent = 1, head[N], cur[N], dis[N];
struct Edge {
    int to, nxt;
    ll fl;
}e[M << 1];
inline void add(int x, int y, int z) {
    e[++ent].to = y; e[ent].fl = z; e[ent].nxt = head[x]; head[x] = ent;
    e[++ent].to = x; e[ent].fl = 0; e[ent].nxt = head[y]; head[y] = ent;
}
bool bfs() {
    for(int i = 1; i <= tot; ++i) dis[i] = -1, cur[i] = head[i];
    std::queue<int>q;
    q.push(S); dis[S] = 0;
    while(!q.empty()) {
        int x = q.front(); q.pop();
        for(int i = head[x]; i; i = e[i].nxt) {
            int v = e[i].to;
            if(dis[v] == -1 && e[i].fl) {
                dis[v] = dis[x] + 1;
                q.push(v);
            }
        }
    }
    return dis[T] != -1;
}
ll dfs(int x, ll lim) {
    if(x == T) return lim;
    ll flow = 0;
    for(int i = cur[x]; i && flow < lim; i = e[i].nxt) {
        int v = e[i].to; cur[x] = i;
        if(dis[v] == dis[x] + 1 && e[i].fl) {
            ll f = dfs(v, Min(e[i].fl, lim - flow));
            flow += f; e[i].fl -= f; e[i^1].fl += f;
        }
    }
    return flow;
}
ll dinic() {
    ll mxfl = 0;
    while(bfs())
        mxfl += dfs(S, INF);
    return mxfl;
}
signed main() {
    read(n, m); S = ++tot; T = ++tot;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            p[i][j] = ++tot;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            read(A[i][j]);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            read(B[i][j]);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            read(C[i][j]);
    ll sum = 0;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j) {
            if((i + j) & 1) {
                add(S, p[i][j], A[i][j]);
                add(p[i][j], T, B[i][j]);
            }
            else {
                add(S, p[i][j], B[i][j]);
                add(p[i][j], T, A[i][j]);
            }
            sum += A[i][j] + B[i][j];
            if(p[i-1][j]) {
                add(p[i-1][j], p[i][j], C[i][j] + C[i-1][j]);
                sum += C[i][j]; 
            }
            if(p[i+1][j]) {
                add(p[i+1][j], p[i][j], C[i][j] + C[i+1][j]);
                sum += C[i][j];
            }
            if(p[i][j-1]) {
                add(p[i][j-1], p[i][j], C[i][j] + C[i][j-1]);
                sum += C[i][j]; 
            }
            if(p[i][j+1]) {
                add(p[i][j+1], p[i][j], C[i][j] + C[i][j+1]);
                sum += C[i][j]; 
            }
        }
    printf("%lld\n", sum - dinic());
    return 0;
}