【网络流】【BZOJ1001】狼抓兔子

继续网络流的学习。。。。

题意简析：就是给你张图，叫你求最小割。

解题思路：最小割=最大流，按题意见图跑一次就好了。

附代码：

#include<cstdio>

#include<iostream>

#include<cstring>

#include<string>

#include<algorithm>

#include<cmath>

#define For(i,a,b) for (int i=a; i<=b; i++)

#define Ford(i,a,b) for (int i=a; i>=b; i--)

#define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);

#define mem(qaq,num) memset(qaq,num,sizeof(qaq));

#define ll long long

#define mod 1000000007

#define INF 90000000000000

using namespace std;

struct zxy{

    int next,to;

    ll v;

}edge[];

int n,m,cnt=,head[],np[],lev[],tt[];

inline int in(){

    int x=,f=;

    char ch=getchar();

    while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();

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

    return x*f;

}

inline int getno(int x,int y){

    return (x-)*m+y;

}

inline void ins(int x,int y,int l){

    edge[++cnt].to=y,edge[cnt].next=head[x],edge[cnt].v=l,head[x]=cnt;

    edge[++cnt].to=x,edge[cnt].next=head[y],edge[cnt].v=l,head[y]=cnt;

}

void read(){

    n=in(),m=in();

    For(i,,n)

        For(j,,m-)

            ins(getno(i,j),getno(i,j+),in());

    For(i,,n-)

        For(j,,m)

            ins(getno(i,j),getno(i+,j),in());

    For(i,,n-)

        For(j,,m-)

            ins(getno(i,j),getno(i+,j+),in());

    return;

}

inline void bfs(){

    int h=,t=;

    mem(lev,);

    lev[]=;

    tt[]=;

    do{

        h++;

        int k=head[tt[h]];

        while(k){

            if (!lev[edge[k].to]&&edge[k].v){

                lev[edge[k].to]=lev[tt[h]]+;

                tt[++t]=edge[k].to;

            }

            k=edge[k].next;

        }

    }while(h<t);

}

ll dfs(int u,int v,ll f){

    if (!(u^v)) return f;

    while(np[u]){

        if (lev[edge[np[u]].to]==lev[u]+&&edge[np[u]].v){

            int d=dfs(edge[np[u]].to,v,min(f,edge[np[u]].v));

            if (d){

                edge[np[u]].v-=d;

                edge[np[u]^].v+=d;

                return d;

            }

        }

        np[u]=edge[np[u]].next;

    }

    return ;

}

ll work(){

    ll flow=;

    for(;;){

        bfs();

        if (!lev[n*m]) return flow;

        For(i,,n*m) np[i]=head[i];

        ll d=dfs(,n*m,INF);

        while(d){

            flow+=d;

            d=dfs(,n*m,INF);

        }

    }

}

int main(){

    read();

    printf("%lld",work());

}

本文由Melacau编写，Melacau代表M星向您问好，如果您不是在我的博客http://www.cnblogs.com/Melacau上看到本文，请您向我联系，email:[email protected].