BZOJ 4808 二分图最大独立集

思路：

棋盘是个二分图

那就把一个可以走的白点  向所有可以走的黑点连边

跑一个最大匹配   （匹配上了就代表这两个点不能共存）

最大独立集=sum-最大匹配

//By SiriusRen

#include <queue>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int N=,M=N*N*;

int n,m,a[N][N],color[N][N],id[N][N],S=,jy,ans,sum;

int first[M],next[M],v[M],w[M],vis[M/],tot,T,cnt;

char xx[]={,-,,-,,-,,-};

char yy[]={,-,,-,-,,-,};

void Add(int x,int y,int z){w[tot]=z,v[tot]=y,next[tot]=first[x],first[x]=tot++;}

void add(int x,int y,int z){Add(x,y,z),Add(y,x,);}

bool tell(){

    memset(vis,-,sizeof(vis));vis[S]=;

    queue<int>q;q.push(S);

    while(!q.empty()){

        int t=q.front();q.pop();

        for(int i=first[t];~i;i=next[i])

            if(w[i]&&vis[v[i]]==-)

                q.push(v[i]),vis[v[i]]=vis[t]+;

    }

    return vis[T]!=-;

}

int zeng(int x,int y){

    if(x==T)return y;

    int r=;

    for(int i=first[x];y>r&&~i;i=next[i])

        if(w[i]&&vis[v[i]]==vis[x]+){

            int t=zeng(v[i],min(y-r,w[i]));

            w[i]-=t,w[i^]+=t,r+=t;

        }

    if(!r)vis[x]=-;

    return r;

}

bool check(int x,int y){

    if(x<||x>n||y<||y>m||a[x][y])return false;

    return true;

}

int main(){

    memset(first,-,sizeof(first));

    scanf("%d%d",&n,&m);T=n*m+;

    for(int i=;i<=n;i++)

        for(int j=;j<=m;j++){

            id[i][j]=++cnt;

            scanf("%d",&a[i][j]);

            if((i+j)&){color[i][j]=,add(S,id[i][j],);}

            else add(id[i][j],T,);

            if(!a[i][j])sum++;

        }

    for(int i=;i<=n;i++)

        for(int j=;j<=m;j++)

            if(color[i][j]&&!a[i][j])

                for(int k=;k<;k++){

                    int tx=i+xx[k],ty=j+yy[k];

                    if(check(tx,ty))add(id[i][j],id[tx][ty],);

                }

    while(tell())while(jy=zeng(S,0x3f3f3f3f))ans+=jy;

    printf("%d\n",sum-ans);

}