【BZOJ 1001】[BeiJing2006] 狼抓兔子

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1001
数据生成器：http://paste.ubuntu.com/18772741/

最大流板题，输入搞反了，调了3hQAQ

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
 
const int N = 1000000+9;
const int INF = 1000000000;
 
inline int read(){
    char c=getchar(); int buf=0,f=1;
    while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while (c<='9'&c>='0'){buf=buf*10+c-'0';c=getchar();}
    return buf*f;
}
 
int n,m,head[N],to[N*6],nxt[N*6],cap[N*6],T,flow[N*6];
int vout,cur[N],que[N],dis[N],fro,bak,tot,s,t;
 
#define id(x,y) (((y)-1)*n+(x))
 
inline void AddEdge(int u, int v, int MX){
    to[++T] = v; nxt[T] = head[u]; head[u] = T; cap[T] = MX;
    to[++T] = u; nxt[T] = head[v]; head[v] = T; cap[T] = MX;
}
 
inline bool BFS(){
    memset(dis,-1,sizeof(dis));
    que[fro=bak=1] = s; dis[s] = 0;
     
    while (bak <= fro) {
        int w = que[bak++];
        for (int i=head[w];i;i=nxt[i]){
            if (flow[i] < cap[i] && dis[to[i]] == -1)
                dis[to[i]] = dis[w]+1,
                que[++fro] = to[i];
        }
    }
    if (dis[t] == -1) return false;
    else return true;
}
 
int MaxFlow(int w, int f){
    if (w==t) {vout += f;return f;}
    else {
        int ret = 0;
        for (int &i=cur[w],tmp;i;i=nxt[i]){
            if (flow[i] < cap[i] && dis[to[i]]==dis[w]+1){
                tmp = MaxFlow(to[i], min(f, cap[i]-flow[i]));
                f -= tmp; ret += tmp;
                flow[i] += tmp; flow[i^1] -= tmp;
                if (!f) return ret;
            }
        }
        return ret;
    }
}
 
inline void Dinic(){
    tot = id(n,m);
    while (BFS()){
        for (int i=1;i<=tot;i++)
            cur[i] = head[i];
        MaxFlow(s,INF);
    }   
}
 
int main(){
    m = read(); n = read(); s = id(1,1); t = id(n,m); T = 1;
    for (int j=1;j<=m;j++) for (int i=1;i<n;i++) AddEdge(id(i,j),id(i+1,j), read());
    for (int j=1;j<m;j++) for (int i=1;i<=n;i++) AddEdge(id(i,j),id(i,j+1), read());
    for (int j=1;j<m;j++) for (int i=1;i<n;i++) AddEdge(id(i,j),id(i+1,j+1),read());
    if (s != t) Dinic();
    printf("%d\n",vout);
    return 0;
}