bzoj 1412: [ZJOI2009]狼和羊的故事

http://www.lydsy.com/JudgeOnline/problem.php?id=1412

超级源点连向所有的狼，超级汇点连向所有羊，流量为INF

相邻连边流量为1，最小割

#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

std::queue<int>que;

int fs[]={,,,-,};

#define INF 0x7fffffff

const int maxn = ;

int map[][];

inline int read() {

    int x=;

    char c=getchar();

    while(c<''||c>'')c=getchar();

    while(c<=''&&c>='')x=x*+c-'',c=getchar();

    return x;

}

int n,m,S,T,src,decc;

struct node{

    int v,next,flow;

}edge[maxn];int head[maxn],num=,cur[maxn],lev[maxn];

void add_edge(int u,int v,int w) {

    edge[++num].v=v;edge[num].next=head[u];head[u]=num;

    edge[num].flow=w;

}

bool bfs() {

    while(!que.empty()) que.pop();

    std::memset(lev,-,sizeof lev);

    memcpy(cur,head,sizeof head);

    lev[src]=;

    que.push(src);int now;

    while(!que.empty()) {

        now=que.front();que.pop();

        for(int i=head[now];i;i=edge[i].next) {

            int v=edge[i].v;

            if(lev[v]==-&&edge[i].flow>) {

                lev[v]=lev[now]+;

                if(v==decc)return true;

                que.push(v);

            }

        }

    }

    return false;

}

int dfs(int now,int flow) {

    if(now==decc)return flow;

    int rest=,delta;

    for(int &i=cur[now];i;i=edge[i].next) {

        int v=edge[i].v;

        if(lev[v]==lev[now]+&&edge[i].flow>) {

            delta=dfs(v,std::min(flow-rest,edge[i].flow));

            if(delta) {

                edge[i].flow-=delta;

                edge[i^].flow+=delta;

                rest+=delta;if(rest==flow)break;

            }

        }

    }

    if(rest==flow)lev[now]=-;//满流

    return rest;

}

int Dinic() {

    int ans=;

    while(bfs())

        ans+=dfs(src,INF);

    return ans;

}

inline void add(int a,int b,int flow) {

    add_edge(a,b,flow);add_edge(b,a,);

}

inline int calc(int i,int j) {

    return (i-)*m+j;

}

int main() {

    n=read(),m=read();

    src=;decc=n*m+;

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

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

            map[i][j]=read();

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

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

            if(map[i][j]==)add(src,calc(i,j),INF);

            else if(map[i][j]==){ add(calc(i,j),decc,INF);continue;}

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

                int x=i+fs[k],y=j+fs[k+];

                if(x<=||x>n||y<=||y>m)continue;

                add(calc(i,j),calc(x,y),);

            }

        }

    }

    printf("%d\n",Dinic());

    return ;

}