【网络流】【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:[e-mail].