记录编号	141477	评测结果	AAAAAA
题目名称	[BJOI2006] 狼抓兔子	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	1.165 s
提交时间	2014-12-01 21:19:05	内存使用	30.38 MiB

#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <set>
#include <queue>
#include <vector>
#include <iterator>
using namespace std;
const int INF=0x7fffffff;
//=====================sturct declare========================
struct adj{
  int from,to,cap,flow;
  adj(int from=0,int to=0,int cap=0,int flow=0):from(from),to(to),cap(cap),flow(flow){}
};
//=====================var declare===========================
const int MAXN=1010*1010;
int col,row,tot=0;
int d[MAXN],gap[MAXN],pa[MAXN],cur[MAXN];
vector <adj> Edge;
vector <int> G[MAXN];
//=====================function declare======================
void add_edge(int from,int to,int cap,int flow);
void bfs();
void isap();
int argument();
//=====================main code=============================
int main()
{
#define FILE__
#ifdef FILE__
   freopen("bjrabbit.in","r",stdin);
   freopen("bjrabbit.out","w",stdout);
#endif
   scanf("%d%d",&row,&col);
   for(int i=1;i<=row;i++)
     for(int j=1;j<col;j++){
       int cap;
       scanf("%d",&cap);
       add_edge((i-1)*col+j,(i-1)*col+j+1,cap,0);
     }
    for(int i=1;i<row;i++)
      for(int j=1;j<=col;j++){
	    int cap;
	    scanf("%d",&cap);
	    add_edge((i-1)*col+j,i*col+j,cap,0);
      }
    for(int i=1;i<row;i++)
      for(int j=1;j<col;j++){
	    int cap;
	    scanf("%d",&cap);
	    add_edge((i-1)*col+j,i*col+j+1,cap,0);
      }
    /*for(int i=2;i<col;i++)  add_edge(0,i,INF,0);
    for(int i=1;i<row;i++)  add_edge(0,i*col,INF,0);
    for(int i=2;i<col;i++)  add_edge(row*col+1,(row-1)*col+i,INF,0);
    for(int i=2;i<=row;i++)  add_edge(1+(i-1)*col,row*col+1,INF,0);*/
   	isap();
}
//======================function code==============
void add_edge(int from,int to,int cap,int flow)
{
   G[from].push_back(tot++);
   G[to].push_back(tot++);
   Edge.push_back(adj(from,to,cap,flow));
   Edge.push_back(adj(to,from,cap,flow));
}
void isap()
{
  memset(d,-1,sizeof(d));memset(cur,0,sizeof(cur));memset(gap,0,sizeof(gap));
  bfs();
  int x=1,flow=0;
  while (d[1]<=row*col+1){
    if (x==row*col){
      flow+=argument();
	  x=1;
	}
	bool suc=false;int siz=G[x].size();
	for(int i=cur[x];i<siz;i++){
      adj &e=Edge[G[x][i]];
	  if (d[e.to]!=d[x]-1) continue;
	  if (e.cap<=e.flow) continue;
	  cur[x]=i;pa[e.to]=G[x][i];
	  x=e.to;suc=true;break;
	}
	if (!suc){
      int mind=row*col+1;
	  for(int i=0;i<siz;i++){
	    adj &e=Edge[G[x][i]];
		if (e.cap<=e.flow) continue;
		  mind=min(d[e.to],mind);
	  }
	  if (--gap[d[x]]==0) break;
	  gap[d[x]=mind+1]++;cur[x]=0;
	  if (x!=1) x=Edge[pa[x]].from;
	}
  }
  printf("%d\n",flow);
}
int argument()
{
  int flow=INF,x=row*col;
  while (x!=1){
    flow=min(flow,Edge[pa[x]].cap-Edge[pa[x]].flow);
	x=Edge[pa[x]].from;
  }
  x=row*col;
  while (x!=1){
    Edge[pa[x]].flow+=flow;
	Edge[pa[x]^1].flow-=flow;
	x=Edge[pa[x]].from;
  }
  return flow;
}
void bfs()
{
   queue <int> Q;d[row*col]=0;Q.push(row*col);
   while (!Q.empty()){
     int x=Q.front();Q.pop();
     gap[d[x]]++;
	 int siz=G[x].size();
	 for(int i=0;i<siz;i++){
	   adj &e=Edge[G[x][i]];
	   if (d[e.to]==-1){
	     d[e.to]=d[x]+1;
		 Q.push(e.to);
	   }
	 }
   }
}