题解 - P2774 方格取数问题

detect · 2019-10-28 17:15:50 · 个人记录

一道不那么容易看出来的网络流最小割题

因为不能与隔壁相连，我们先黑白染下色，我们现在转化一下题意变成了全选状态下至少删去多少个格子是的不连通，是不是有点像最小割了！

对于实现：超级源点对所有白色连一条入边容量为权值，所有黑格子连一条出边至超级汇点，然后对于相邻的边连一条容量无线大的边，这样既保证连通性也保证被割的边不会是它，于是对于我们建出来的图的最小割意义就是，删去一些格子，使得相邻的格子没有相交，于是我们目的达到了，跑一遍最大流求解最小割就行了

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
int head[100000],nex[100000],w[100000],go[100000],dep[100005];
int f[4][2]={{1,0},{0,1},{0,-1},{-1,0}};
int S,T,ssum,tot=1,n,m,a[105][105];
inline int gn(int x,int y){
    return (x-1)*m+y;
}
void add(int u,int v,int val){
    nex[++tot]=head[u];head[u]=tot;go[tot]=v;w[tot]=val;
}
bool bfs(){
    queue <int> q;
    q.push(S);
    memset(dep,-1,sizeof(dep));
    dep[S]=0;
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=head[u];i;i=nex[i]){
            int v=go[i];
            if(dep[v]==-1&&w[i]){
                dep[v]=dep[u]+1;
                q.push(v);
            }
        }
    }
    return dep[T]!=-1;
}
int dfs(int u,int lim){
    if(u==T) return lim;
    int res=0;
    for(int i=head[u];i;i=nex[i]){
        int v=go[i];
        if(dep[v]==dep[u]+1&&w[i]){
            int sum=0;
            sum=dfs(v,min(lim-res,w[i]));
            if(sum){
                res+=sum;
                w[i]-=sum;
                w[i^1]+=sum;
            }
        }   
    }
    return res;
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
        scanf("%lld",&a[i][j]),ssum+=a[i][j];
    S=0,T=n*m+1;
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++){
        if((i+j)%2==0){
            add(S,gn(i,j),a[i][j]);
            add(gn(i,j),S,0);
        }
        else{
            add(gn(i,j),T,a[i][j]);
            add(T,gn(i,j),0);
        }
      }
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++){
        if((i+j)%2==0)
        for(int k=0;k<=3;k++){
            int xx=i+f[k][0];
            int yy=j+f[k][1];
            if(xx<=0||yy<=0||xx>n||yy>m) continue;
            add(gn(i,j),gn(xx,yy),1e9);
            add(gn(xx,yy),gn(i,j),0);
        }
      }
    int ans=0;
    while(bfs()){
        ans+=dfs(S,1e18);
    }
    cout<<ssum-ans<<"\n";
    return 0;
}