1001: [BeiJing2006]狼抓兔子
题目：
题解：
听说这题当初是大难题...可惜当年没有网络流hahahha
现在用网络流的思想就很容易解决了嘛
给什么连什么，注意是双向边，然后跑最大流...AC
代码：
1 #include2 #include 3 #include 4 #include 5 #include 6 #define N 1100000 7 using namespace std; 8 struct node 9 {10 int x,y,c,next,other;11 }a[6110000];int len,last[3110000];12 int n,m,head,tail,st,ed;13 void ins(int x,int y,int c)14 {15 int k1,k2;16 len++;k1=len;17 a[len].x=x;a[len].y=y;a[len].c=c;18 a[len].next=last[x];last[x]=len;19 20 len++;k2=len;21 a[len].x=y;a[len].y=x;a[len].c=c;22 a[len].next=last[y];last[y]=len;23 24 a[k1].other=k2;25 a[k2].other=k1;26 }27 int list[3110000],h[3110000];28 bool bt_h()29 {30 memset(h,0,sizeof(h));h[st]=1;31 list[1]=st;head=1;tail=2;32 while(head!=tail)33 {34 int x=list[head];35 for(int k=last[x];k;k=a[k].next)36 {37 int y=a[k].y;38 if(h[y]==0 && a[k].c>0)39 {40 h[y]=h[x]+1;41 list[tail++]=y;42 }43 }44 head++;45 }46 if(h[ed]>0)return true;47 return false;48 }49 int find_flow(int x,int flow)50 {51 if(x==ed)return flow;52 int s=0,t;53 for(int k=last[x];k;k=a[k].next)54 {55 int y=a[k].y;56 if(h[y]==h[x]+1 && a[k].c>0 && flow>s)57 {58 t=find_flow(y,min(a[k].c,flow-s));59 s+=t;60 a[k].c-=t;a[a[k].other].c+=t;61 }62 }63 if(s==0)h[x]=0;64 return s;65 }66 int main()67 {68 while(scanf("%d%d",&n,&m)!=EOF)69 {70 len=0;memset(last,0,sizeof(last));71 st=1;ed=n*m;72 for(int i=1;i<=n;i++)73 for(int j=1;j