题目概述

有 $n\times n$ 的网格，如果 $(i,j)$ 满足 $i+j$ 是奇数那么这个格子就有危险度，现在可以放 $m$ 个占地为 $3$ 的 $L$ 型的石头，石头拐点处的危险度会清零，但石头不能重叠且不能放在有障碍的地方，求最小的危险度和。

解题报告

肯定会把石头拐点放在有危险度的地方，由于石头不能重叠比较复杂，所以我们可以考虑用网络流进行资源分配。

将没有危险度的格子称为空点，一种放石头的方案对应着源点->空点A->有危险度的格子B->空点C->汇点（其中 $A,B,C$ 相邻），但是如果按照这样直接建边就会出现环导致GG，而相邻空点横纵坐标一定相差 $1$ ，所以根据套路可以将空点奇偶拆分（横纵坐标都可以）后再建边，这样就没有环了。

然后要注意带点权的是有危险度的格子，所以需要拆点的是有危险度的格子而不是空点！！！而且不一定石头选的越多越好，一旦最短路变成了负数，说明已经开始退流了（因为费用流是在最大流的基础上保证费用），可以直接停止，求出最大费用可行流。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=50,maxt=maxn*maxn<<1,maxm=(maxt<<3)+(maxt<<1);

int n,m,K,pic[maxn+5][maxn+5],ans;bool ban[maxn+5][maxn+5];
int E,lnk[maxt+5],son[(maxm<<1)+5],nxt[(maxm<<1)+5],e[(maxm<<1)+5],w[(maxm<<1)+5];
int S,T,ID[maxn+5][maxn+5],que[maxt+5],ti,vis[maxt+5],dis[maxt+5],MIN[maxt+5];

inline void Add(int x,int y,int z,int c){
    son[E]=y;e[E]=z;w[E]=c;nxt[E]=lnk[x];lnk[x]=E++;
    son[E]=x;e[E]=0;w[E]=-c;nxt[E]=lnk[y];lnk[y]=E++;
}
#define AM(x) ((x)<maxt?(x)+1:0)
inline bool Spfa(int s,int t,int &MC){
    static int fa[maxt+5],pre[maxt+5];for (int i=S;i<=T;i++) dis[i]=-2e9;
    int Head=0,Tail=0;que[Tail=AM(Tail)]=s;vis[s]=++ti;dis[s]=0;MIN[s]=MIN[t]=2e9;
    while (Head!=Tail){
        int x=que[Head=AM(Head)];vis[x]=0;
        for (int j=lnk[x],u;~j;j=nxt[j])
            if (e[j]&&dis[x]+w[j]>dis[u=son[j]]){
                dis[u]=dis[x]+w[j];MIN[u]=min(MIN[x],e[j]);
                fa[u]=x;pre[u]=j;if (vis[u]<ti) que[Tail=AM(Tail)]=u,vis[u]=ti;
            }
    }if (MIN[t]==2e9) return false;if (dis[t]<=0) return false;MC+=dis[t]*MIN[t];
    for (int x=t,j;x!=s;x=fa[x]) j=pre[x],e[j]-=MIN[t],e[j^1]+=MIN[t];return true;
}
inline int MCMF(int S,int T) {int MC=0;while (Spfa(S,T,MC));return MC;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d%d",&n,&m,&K);
    for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) scanf("%d",&pic[i][j]),ans+=pic[i][j];
    for (int i=1,x,y;i<=K;i++) scanf("%d%d",&x,&y),ban[x][y]=true;
    K=1;for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) K+=(i+j&1)<<1;
    for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if ((i+j&1^1)&&!ban[i][j]) ID[i][j]=++K;
    S=0;T=K+1;E=0;for (int i=S;i<=T;i++) lnk[i]=-1;Add(S,1,m,0);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            if (ID[i][j]) i&1?Add(1,ID[i][j],1,0):Add(ID[i][j],T,1,0);
    for (int i=1,cnt=0;i<=n;i++)
        for (int j=1,A,B;j<=n;j++)
            if (i+j&1){
                cnt+=2;Add(cnt,cnt+1,1,pic[i][j]);
                if ((A=ID[i-1][j])&&(B=ID[i][j-1])) {if (i&1) swap(A,B);Add(A,cnt,1,0);Add(cnt+1,B,1,0);}
                if ((A=ID[i-1][j])&&(B=ID[i][j+1])) {if (i&1) swap(A,B);Add(A,cnt,1,0);Add(cnt+1,B,1,0);}
                if ((A=ID[i+1][j])&&(B=ID[i][j-1])) {if (i&1) swap(A,B);Add(A,cnt,1,0);Add(cnt+1,B,1,0);}
                if ((A=ID[i+1][j])&&(B=ID[i][j+1])) {if (i&1) swap(A,B);Add(A,cnt,1,0);Add(cnt+1,B,1,0);}
            }
    printf("%d\n",ans-MCMF(S,T));return 0;
}