【费用流】[JZOJ5823] marshland

Description

石头不能重叠。

Solution

这种奇怪的不好做的题，一般几种思路。
贪心结论，暴力，状压DP，网络流。
结论我们找不到。。。
暴力只有10分
状压DP明显状态数爆表。
剩下的选择只有网络流

首先L的拐角一定会放在X+Y为奇数的格子上。
考虑一个L形石头的本质，它一定能表示为一个X+Y为偶数且X为奇数的点−>$->$X+Y为奇数的点−>$->$X+Y为偶数且X为偶数的点这么一个顺序。

黑白染色，令X+Y为偶数的点为白点，X+Y为奇数的点为黑点。奇白点表示白点中X为奇数的点，偶白点类似
将黑点拆成出点的和入点，入点向出点连流量为 1，费用为这个值的边

每个黑点相邻的奇白点连向这个黑点的入点，黑点的出点连向相邻的偶白点。费用为0，容量都为1

源点向每个奇白点连费用0容量1，每个偶白点向汇点连费用0容量1

这样跑最大费用可行流，直到增广了m次或者增广路长度为负则退出，用总和减去就是答案。

Solution

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <vector>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
#define N 55
#define M 4205
using namespace std;
bool bz[N][N];
int pr[N][N],m1,n,m,n1,st,ed,l,fx[4][2]={{-1,0},{0,1},{1,0},{0,-1}},f[M][M],ans,mx,c[M][M],in[N][N],out[N][N],wz[N][N],dis[M],d[100*M],g[M],fs[M],nt[10*M],dt[10*M];
bool b1[M];
void link(int x,int y,int z,int p)
{
    nt[++m1]=fs[x];
    dt[fs[x]=m1]=y;

    nt[++m1]=fs[y];
    dt[fs[y]=m1]=x;

    f[x][y]+=z;
    c[x][y]=p;
    c[y][x]=-p;
}
bool spfa()
{
    fo(j,1,n1) dis[j]=-100000000;
    memset(g,0,sizeof(g));
    memset(b1,0,sizeof(bz));
    dis[st]=0,b1[st]=1;
    int l=0,r=1;
    d[r]=st;
    while(l<r)
    {
        int k=d[++l];
        for(int i=fs[k];i;i=nt[i])
        {
            int j=dt[i];
            if(f[k][j]&&dis[k]+c[k][j]>dis[j])
            {
                dis[j]=dis[k]+c[k][j],g[j]=k;
                if(!b1[j]) b1[j]=1,d[++r]=j;
            }
        }
        b1[k]=0;
    }
    return(dis[ed]>0);
}
void get()
{
    int k=ed;
    while(g[k]>0)
    {
        ans+=c[g[k]][k];
        f[g[k]][k]--,f[k][g[k]]++;
        k=g[k];
    }
}
int main()
{
    freopen("marshland.in","r",stdin);
    freopen("marshland.out","w",stdout);
    cin>>n>>m>>l;
    n1=2,st=1,ed=2;
    fo(i,1,n)
    {
        fo(j,1,n) 
        {
            scanf("%d",&pr[i][j]),mx+=pr[i][j];
        }
    }
    fo(i,1,l)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        bz[x][y]=1;
    }
    fo(i,1,n)
    {
        fo(j,1,n)
        {
            if(pr[i][j]>0)
            {
                in[i][j]=++n1,out[i][j]=++n1;
                link(n1-1,n1,1,pr[i][j]);
            }   
            else if(!bz[i][j]&&(i+j)%2==0)
            {
                wz[i][j]=++n1;
                if(i%2==0) link(n1,ed,1,0);
                else link(st,n1,1,0);
            }
        }
    }
    fo(i,1,n)
    {
        fo(j,1,n)
        {
            if(pr[i][j]>0)
            {
                fo(k,0,3)
                {
                    int p=i+fx[k][0],q=j+fx[k][1];
                    if(p>0&&q>0&&p<=n&&q<=n&&(!bz[p][q]))
                    {
                        if(p%2) link(wz[p][q],in[i][j],1,0);
                        else link(out[i][j],wz[p][q],1,0); 
                    }
                }
            }
        }
    }
    int cnt=0;
    ans=0;
    while(cnt<m&&spfa()) 
        get(),cnt++;
    printf("%d\n",mx-ans);
}