[COGS 2051] 王者之剑题解网络流最大权闭合子图

【题目描述】

这是在阿尔托利亚·潘德拉贡成为英灵前的事情，她正要去拔出石中剑成为亚瑟王，在这之前她要去收集一些宝石。
宝石排列在一个n*m的网格中，每个网格中有一块价值为v(i,j)的宝石，阿尔托利亚·潘德拉贡可以选择自己的起点。
开始时刻为0秒。以下操作，每秒按顺序执行
1.在第i秒开始的时候，阿尔托利亚·潘德拉贡在方格（x,y）上，她可以拿走（x，y）中的宝石。
2.在偶数秒，阿尔托利亚·潘德拉贡周围四格的宝石会消失
3.若阿尔托利亚·潘德拉贡第i秒开始时在方格（x，y）上，则在第i+1秒可以立即移动到（x+1，y），（x，y+1），（x-1，y）或（x，y-1）上，也可以停留在（x,y)上。
求阿尔托利亚·潘德拉贡最多可以获得多少价值的宝石

【输入格式】

第一行给出数字N,M代表行列数.N,M均小于等于100，宝石的价值不会超过10000.下面N行M列用于描述数字矩阵

【输出格式】

输出最多可以拿到多少价值宝石

【样例输入】

2 2
1 2
2 1

【样例输出】

与网络流24题中方格取数相同
最大权闭合子图
黑白染色
相邻连INF的边
源点向白格子连格子权值的边
黑格子想汇点连权值的边

跑一遍最小割也就是最大流
Dinic解决

/*
 * @Author: WildRage 
 * @Date: 2017-06-13 16:37:09 
 * @Last Modified by:   WildRage 
 * @Last Modified time: 2017-06-13 16:37:09 
 */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int INF=0x7fffffff;
struct edge{
    int END,cap,next;
}v[500000];
int first[10005],p;
void add(int a,int b,int c){
    v[p].END=b;v[p].next=first[a];v[p].cap=c;first[a]=p++;
    v[p].END=a;v[p].next=first[b];v[p].cap=0;first[b]=p++;
}
int dis[10005];
bool vis[10005];
bool BFS(int S,int E){
    memset(vis,0,sizeof(vis));
    memset(dis,-1,sizeof(dis));
    queue<int> Q;
    Q.push(S);
    dis[S]=0;vis[S]=1;
    while(!Q.empty()){
        int u=Q.front();Q.pop();
        for(int i=first[u];i!=-1;i=v[i].next){
            if(!vis[v[i].END]&&v[i].cap>0){
                vis[v[i].END]=1;
                dis[v[i].END]=dis[u]+1;
                if(v[i].END==E)return 1;
                Q.push(v[i].END);
            }
        }
    }
    return 0;
}
int DFS(int x,int a,int E){
    if(x==E||a==0)return a;
    int flow=0,f;
    for(int i=first[x];i!=-1;i=v[i].next){
        if(dis[x]+1==dis[v[i].END]&&(f=DFS(v[i].END,min(a,v[i].cap),E))>0){
            v[i].cap-=f;
            v[i^1].cap+=f;
            flow+=f;
            a-=f;
            if(a==0)break;
        }
    }
    if(!flow)dis[x]=-1;
    return flow;
}
int Dinic(int S,int E){
    int flow=0;
    while(BFS(S,E)){
        flow+=DFS(S,INF,E);
    }
    return flow;
}
int a[105][105];
template<class T>inline void read(T &res){
    static char ch;T flag=1;
    while((ch=getchar())<'0'||ch>'9')if(ch=='-')flag=-1;res=ch-48;
    while((ch=getchar())>='0'&&ch<='9')res=(res<<1)+(res<<3)+ch-48;res*=flag;
}
int Main(){
    freopen("Excalibur.in","r",stdin);
    freopen("Excalibur.out","w",stdout);
    memset(first,-1,sizeof(first));
    int m,n;
    int sum=0;
    read(m),read(n);
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++){
            read(a[i][j]);
            sum+=a[i][j];
        }
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            if((i&1)^(j&1)){
                add(0,n*(i-1)+j,a[i][j]);
                if(j-1>=1)add(n*(i-1)+j,n*(i-1)+j-1,INF);
                if(i-1>=1)add(n*(i-1)+j,n*(i-2)+j,INF);
                if(i+1<=m)add(n*(i-1)+j,n*(i)+j,INF);
                if(j+1<=n)add(n*(i-1)+j,n*(i-1)+j+1,INF);
            }
            else{
                add(n*(i-1)+j,n*m+1,a[i][j]);
            }
            
        }
    }
    return printf("%d",sum-Dinic(0,m*n+1));
}
int A=Main();
int main(){;}