题解 P6094 【[JSOI2015]圈地】

Rusalka · 2020-07-27 23:51:32 · 题解

原题链接：P6094 [JSOI2015]圈地

题意简述

把一块 n \times m 的地分给两个人，选择分出第 i 行第 j 列的地可以获得 a_{i,j} 的收益。
要在两个人分到的地中间建墙，使得两个人分到的地完全隔离，建两个格子之间的墙需要花费一定代价。
最大化总收益与总代价的差
1 \le n, m \le 200
~~细节还是见原题吧QAQ~~

思路与解答

~~你看它数据范围这么小肯定是个图论建模，而且大概率网络流~~
你看这题相当于要把地分成两块，并且代价最小。
那就是一个最小割嘛
然后考虑怎么建图
你在建图时需要保证能选或不选一块地，并且要能够“割”开两块属于不同的人的地
假设两个人分别为 A 和 B，那么首先把相邻两块地之间连边，流量为建墙的花费，表示如果要“割”开这两块地就要砍掉这条边，当然要不要砍再说；注意这里无法保证你要怎么“割”，所以两块地要分别向对方连边。
那么之后建一个超级源点 S，把 S 和所有 A 想要的地连边，流量为这块地的收益，如果在权衡之后不选，就把这条边“割”掉；同理，把所有 B 想要的地和超级汇点 T 连边，流量也为这块地的收益。
那么你在这张图中跑一遍最小割，得到的结果就是你需要付出的最小代价，这里是包括了选或者不选一块地。
所以你只需要把总收益，即所有结点的收益和减去最小割即可。
最后，你只需要知道最小割等于最大流，就可以愉快的切题了

Code

#include <cstdio>
#include <queue>
#include <iostream>
#include <cstring>
#define abs(x) (x<0?-x:x)

using namespace std;

const int MAXN = 80010;
const int INF = 0x3f3f3f3f; 

int n, m;

inline int id(int i, int j){return (i-1)*m+j;}

struct edge{
    int ne, to, fl;
    edge(int N=0,int T=0,int F=0):ne(N),to(T),fl(F){}
}e[MAXN*6];
int fir[MAXN], num = 1;
int s, t;
inline void adde(int a, int b, int c)
{
    e[++num] = edge(fir[a], b, c);
    fir[a] = num;
}
inline void join(int a, int b, int c)
{
    adde(a, b, c);
    adde(b, a, 0);
}

int dep[MAXN], cur[MAXN];
queue<int> q;
bool bfs(int s, int t)
{
    for(int i=0;i<=n*m+1;i++)
        dep[i] = 0, cur[i] = fir[i];
    while(!q.empty()) q.pop();
    q.push(s);
    dep[s] = 1;
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(int i=fir[u];i;i=e[i].ne)
        {
            int v = e[i].to;
            if(dep[v] || !e[i].fl) continue;
            dep[v] = dep[u] + 1;
            q.push(v);
        }
    }
    return dep[t];
}
int dfs(int u, int fln)
{
    if(u == t) return fln;
    int res = 0;
    for(int& i=cur[u];i;i=e[i].ne)
    {
        int v = e[i].to;
        if(!e[i].fl || dep[v] != dep[u]+1) continue;
        int sum = dfs(v, min(fln, e[i].fl));
        e[i].fl -= sum;
        e[i^1].fl += sum;
        fln -= sum;
        res += sum;
        if(!fln) break;
    }
    if(!res) dep[u] = 0;
    return res;
}
inline int dinic()
{
    int res = 0;
    while(bfs(s, t)) res += dfs(s, INF);
    return res;
}

int main()
{
    scanf("%d%d",&n,&m);
    s = 0; t = n*m+1;
    int sum = 0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int a;
            scanf("%d",&a);
            if(a > 0) join(s, id(i, j), a);
            if(a < 0) join(id(i, j), t, -a);
            sum += abs(a);
        }
    }
    for(int i=1;i<n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int a;
            scanf("%d",&a);
            join(id(i, j), id(i+1, j), a);
            join(id(i+1, j), id(i, j), a);
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<m;j++)
        {
            int a;
            scanf("%d",&a);
            join(id(i, j), id(i, j+1), a);
            join(id(i, j+1), id(i, j), a);
        }
    }
    printf("%d\n",sum-dinic());
    return 0;
}