bzoj1001: [BeiJing2006]狼抓兔子（初识是你最小割）

1001: [BeiJing2006]狼抓兔子

题目：传送门

题解：

　　 听说这题当初是大难题...可惜当年没有网络流hahahha

　　 现在用网络流的思想就很容易解决了嘛

　　 给什么连什么，注意是双向边，然后跑最大流...AC

代码：

　　

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<algorithm>

 #define N 1100000

 using namespace std;

 struct node

 {

     int x,y,c,next,other;

 }a[];int len,last[];

 int n,m,head,tail,st,ed;

 void ins(int x,int y,int c)

 {

     int k1,k2;

     len++;k1=len;

     a[len].x=x;a[len].y=y;a[len].c=c;

     a[len].next=last[x];last[x]=len;

     len++;k2=len;

     a[len].x=y;a[len].y=x;a[len].c=c;

     a[len].next=last[y];last[y]=len;

     a[k1].other=k2;

     a[k2].other=k1;

 }

 int list[],h[];

 bool bt_h()

 {

     memset(h,,sizeof(h));h[st]=;

     list[]=st;head=;tail=;

     while(head!=tail)

     {

         int x=list[head];

         for(int k=last[x];k;k=a[k].next)

         {

             int y=a[k].y;

             if(h[y]== && a[k].c>)

             {

                 h[y]=h[x]+;

                 list[tail++]=y;

             }

         }

         head++;

     }

     if(h[ed]>)return true;

     return false;

 }

 int find_flow(int x,int flow)

 {

     if(x==ed)return flow;

     int s=,t;

     for(int k=last[x];k;k=a[k].next)

     {

         int y=a[k].y;

         if(h[y]==h[x]+ && a[k].c> && flow>s)

         {

             t=find_flow(y,min(a[k].c,flow-s));

             s+=t;

             a[k].c-=t;a[a[k].other].c+=t;

         }

     }

     if(s==)h[x]=;

     return s;

 }

 int main()

 {

     while(scanf("%d%d",&n,&m)!=EOF)

     {

         len=;memset(last,,sizeof(last));

         st=;ed=n*m;

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

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

             {

                 int t;

                 scanf("%d",&t);

                 ins((i-)*m+j,(i-)*m+j+,t);

             }

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

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

             {

                 int t;

                 scanf("%d",&t);

                 ins((i-)*m+j,i*m+j,t);

             }

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

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

             {

                 int t;

                 scanf("%d",&t);

                 ins((i-)*m+j,i*m+j+,t);

             }

         int ans=;

         while(bt_h())ans+=find_flow(st,);

         printf("%d\n",ans);

     }

     return ;

 }