[BZOJ 1412] 狼与羊的故事

Link:

BZOJ 1412 传送门

Solution:

非常明显的最小割模型：

将所有点分成两个互不相邻的点集，且要求代价最小

建图：

$<S,sheep,INF>$

$<wolf,T,INF>$

$<sheep,wolf/ground,1>$、$<ground,wolf/sheep/ground,1>$

Code:

#include <bits/stdc++.h>

using namespace std;

const int MAXN=,MAXM=,INF=<<;

namespace Max_Flow

{

    int head[MAXN],S,T,level[MAXN],iter[MAXN],tot=-;

    struct edge{int nxt,to,cap;}e[MAXM<<];

    void add_edge(int from,int to,int cap)

    {

        e[++tot].nxt=head[from];e[tot].to=to;e[tot].cap=cap;head[from]=tot;

        e[++tot].nxt=head[to];e[tot].to=from;e[tot].cap=;head[to]=tot;

    }

    bool bfs()

    {

        memset(level,-,sizeof(level));

        queue<int> q;q.push(S);level[S]=;

        while(!q.empty())

        {

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

            for(int i=head[u];i!=-;i=e[i].nxt)

                if(e[i].cap && level[e[i].to]==-)

                    level[e[i].to]=level[u]+,q.push(e[i].to);

        }

        return (level[T]!=-);

    }

    int dfs(int v,int f)

    {

        if(v==T) return f;

        int ret=;

        for(int &i=iter[v];i!=-;i=e[i].nxt)

        {

            if(level[e[i].to]==level[v]+ && e[i].cap)

            {

                int d=dfs(e[i].to,min(f,e[i].cap));

                e[i].cap-=d;e[i^].cap+=d;

                f-=d;ret+=d;if(!f) break;

            }

        }

        return ret;

    }

    int Dinic()

    {

        int ret=;

        while(bfs())

        {

            for(int i=;i<MAXN;i++) iter[i]=head[i];

            ret+=dfs(S,INF);

        }

        return ret;

    }

}

int dx[]={,-,,},dy[]={,,,-};

int n,m,dat[][];

int main()

{

    using namespace Max_Flow;

    S=;T=;memset(head,-,sizeof(head));

    scanf("%d%d",&n,&m);

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

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

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

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

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

        {

            if(dat[i][j]==) add_edge(S,(i-)*m+j,INF);

            if(dat[i][j]==){add_edge((i-)*m+j,T,INF);continue;}

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

            {

                int fx=i+dx[k],fy=j+dy[k];

                if(fx<||fx>n||fy<||fy>m) continue;

                if(dat[i][j]!= || dat[fx][fy]!=)

                    add_edge((i-)*m+j,(fx-)*m+fy,);

            }

        }

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

    return ;

}