题目概述

有 $n\times m$ 的网格，有两种方法占领一个格子：1.花费 $c_{i,j}$ 。2.该格子上下左右的格子已经被占领。占领一个格子之后有 $b_{i,j}$ 的收益，求收益减去花费的最大值。

解题报告

数据范围小的可怜，但是状压显然没法做……所以想到网络流。

然后一直在想最大权闭合图，就GG了……其实只要直接最小割套路就行了……

先假装所有点都已经占领了，但是很明显不合法，所以对于一个点要么买下来要么把周围的买下来，或者抛弃收益。

这个其实挺好建边的，把一个点拆成两个，入点向出点连收益的边，源点向入点连花费的边，再从入点向相邻节点的出点连边？然后就出现了一口大锅：成环了。

所以需要对网格进行黑白染色，源点连向白色点的入点，黑色点的出点连向汇点就没有问题了。

图长这样：（感谢法老的图）

示例程序

#include<cstdio>
#include<cctype>
#include<string>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=20,maxt=maxn*maxn*2,maxe=maxt*12;

int n,m,a[maxn+5][maxn+5],b[maxn+5][maxn+5],S,T,ans;
int E,lnk[maxt+5],son[maxe+5],nxt[maxe+5],e[maxe+5];
int que[maxt+5],ti,vis[maxt+5],dis[maxt+5],cur[maxt+5];

#define ID(i,j,k) (((i)*m+(j)-m<<1)-(k))
class SurroundingGame{
public:
    inline void Add(int x,int y,int z){
        son[E]=y;e[E]=z;nxt[E]=lnk[x];lnk[x]=E++;
        son[E]=x;e[E]=0;nxt[E]=lnk[y];lnk[y]=E++;
    }
    inline bool Bfs(int s,int t){
        int Head=0,Tail=0;que[++Tail]=s;vis[s]=++ti;dis[s]=0;cur[s]=lnk[s];
        while (Head!=Tail)
            for (int x=que[++Head],j=lnk[x],u;~j;j=nxt[j])
                if (vis[u=son[j]]<ti&&e[j]) que[++Tail]=u,vis[u]=ti,dis[u]=dis[x]+1,cur[u]=lnk[u];
        return vis[t]==ti;
    }
    int Dfs(int x,int t,int MIN=2e9){
        if (x==t||!MIN) return MIN;int f=0,now;
        for (int &j=cur[x];~j;j=nxt[j])
            if (dis[x]+1==dis[son[j]]&&(now=Dfs(son[j],t,min(MIN,e[j]))))
                {f+=now;e[j]-=now;e[j^1]+=now;if (!(MIN-=now)) break;}return f;
    }
    inline int Dinic(int s,int t) {int ans=0;while (Bfs(s,t)) ans+=Dfs(s,t);return ans;}
    inline int val(char ch) {if (isdigit(ch)) return ch-'0';if (islower(ch)) return ch-'a'+10;return ch-'A'+36;}
    int maxScore(vector<string> B,vector<string> A){
        n=A.size();m=A[0].length();S=0;T=n*m<<1|1;memset(lnk,255,sizeof(lnk));
        for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) b[i][j]=val(B[i-1][j-1]);
        for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) a[i][j]=val(A[i-1][j-1]),ans+=a[i][j];
        for (int i=1;i<=n;i++)
            for (int j=1;j<=m;j++)
                if (i+j&1){
                    Add(S,ID(i,j,0),b[i][j]);Add(ID(i,j,0),ID(i,j,1),a[i][j]);
                    if (i>1) Add(ID(i,j,0),ID(i-1,j,0),2e9);if (i<n) Add(ID(i,j,0),ID(i+1,j,0),2e9);
                    if (j>1) Add(ID(i,j,0),ID(i,j-1,0),2e9);if (j<m) Add(ID(i,j,0),ID(i,j+1,0),2e9);
                } else{
                    Add(ID(i,j,1),T,b[i][j]);Add(ID(i,j,0),ID(i,j,1),a[i][j]);
                    if (i>1) Add(ID(i-1,j,1),ID(i,j,1),2e9);if (i<n) Add(ID(i+1,j,1),ID(i,j,1),2e9);
                    if (j>1) Add(ID(i,j-1,1),ID(i,j,1),2e9);if (j<m) Add(ID(i,j+1,1),ID(i,j,1),2e9);
                }
        return ans-Dinic(S,T);
    }
};