「BZOJ 1001」狼抓兔子

题目链接

luogu
bzoj

(Solution)

这个貌似没有什么好讲的吧,直接按照这个给的图建图就好了啊,没有什么脑子,但是几点要注意的:

1. 建双向边啊.
2. 要这么写,中间还要写一个(while)否则会(T)的:

while(bfs()){
		while((k=dfs(s,inf)))
			ans+=k;
    }

(Code)

#include<bits/stdc++.h>
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
#define rg register
using namespace std;
typedef long long ll;
const int inf=1e9;
int n,m,s=1,t=26,z,y,x;
inline int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9')  f= (c=='-')?-1:1,c=getchar();
    while(c>='0'&&c<='9')  x=x*10+c-48,c=getchar();
    return f*x;
}
struct node{
    int to,next,v;
}a[6000001];
int cnt,head[1000001];
void add(int x,int y,int c){
    a[++cnt].to=y,a[cnt].next=head[x],a[cnt].v=c,head[x]=cnt;
    a[++cnt].to=x,a[cnt].next=head[y],a[cnt].v=c,head[y]=cnt;
}
queue<int>q;
int dep[1000001];
int bfs(){
    memset(dep,0,sizeof(dep));
    q.push(s),dep[s]=1;
    while(!q.empty()){
        int now=q.front();
        q.pop();
        for(int i=head[now];i;i=a[i].next){
            int v=a[i].to;
            if(!dep[v]&&a[i].v)
                q.push(v),dep[v]=dep[now]+1;
        }
    }
    return dep[t]?1:0;
}
int dfs(int k,int list){
    if(k==t)
        return list;
    for(int i=head[k];i;i=a[i].next){
        int v=a[i].to;
        if(a[i].v&&dep[v]==dep[k]+1){
            int p=dfs(v,min(list,a[i].v));
            if(p){
                a[i].v-=p;
                if(i&1)
                    a[i+1].v+=p;
                else a[i-1].v+=p;
                return p;
            }
        }
    }
    dep[k]=0;
    return 0;
}
int Dinic(){
    int ans=0,k;
    while(bfs()){
		while((k=dfs(s,inf)))
			ans+=k;
    }
    return ans;
}
int main(){
    n=read(),m=read(),s=1,t=n*m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<m;j++)
            z=read(),x=(i-1)*m+j,y=x+1,add(x,y,z);
    for(int i=1;i<n;i++)
        for(int j=1;j<=m;j++)
            z=read(),x=(i-1)*m+j,y=x+m,add(x,y,z);
    for(int i=1;i<n;i++)
        for(int j=1;j<m;j++)
            z=read(),x=(i-1)*m+j,y=x+m+1,add(x,y,z);
    int ans=Dinic();
    printf("%d",ans);
}