「BZOJ 1001」狼抓兔子

题目链接

\(Solution\)

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

建双向边啊.
要这么写,中间还要写一个\(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);

}

巴特西

「BZOJ 1001」狼抓兔子

题目链接

\(Solution\)

\(Code\)

最新文章

热门文章