[ICPC-Beijing 2006]狼抓兔子

题意

求最小割

题解

Dinic+当前弧优化

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int n,m,S,T,cnt=-1,depth[6000001],head[6000001];
int cur[6000001];
struct edge{
    int nxt=-1,to,w;
}flow[6000001];
void add(int x,int y,int z){
    cnt++;
    flow[cnt].to=y;
    flow[cnt].w=z;
    flow[cnt].nxt=head[x];
    head[x]=cnt;
}
bool bfs(){    
    queue<int> q;
    while (!q.empty()) q.pop();
    memset(depth,0,sizeof(depth));
    depth[S]=1;        
    q.push(S);
    while (!q.empty()){  
        int u=q.front();  
        q.pop();
        for (int i=head[u];i!=-1;i=flow[i].nxt)
            if ((flow[i].w>0)&&(depth[flow[i].to]==0)){
                depth[flow[i].to]=depth[u]+1; 
                q.push(flow[i].to);
            } 
    }
    if (depth[T]==0){    
        return false;
    }    
    return true;
}
int dfs(int u,int dist){
    if (u==T) return dist;
    for (int &i=cur[u];i!=-1;i=flow[i].nxt){
        if ((depth[flow[i].to]==depth[u]+1)&&(flow[i].w!=0)) { 
            int di=dfs(flow[i].to,min(dist,flow[i].w));
            if (di>0){
                flow[i].w-=di;
                flow[i^1].w+=di; 
                return di; 
            }
        } 
    } 
    return 0;
}
int Dinic(){
    int ans=0;
    while (bfs()){ 
    memcpy(cur,head,sizeof(head));
        while (int d=dfs(S,1e8))
            ans+=d;
    }
    return ans;
}
int point(int x,int y){
    return (x-1)*m+y;
}

int main(){
    memset(head,-1,sizeof(head));
    cin>>n>>m;
    S=point(1,1);
    T=point(n,m);
    int x;
    for (int i=1;i<=n;i++)
        for (int j=1;j<m;j++){
            cin>>x;
            add(point(i,j),point(i,j+1),x);
            add(point(i,j+1),point(i,j),x);
        }
    for (int i=1;i<n;i++)
        for (int j=1;j<=m;j++){
            cin>>x;
            add(point(i,j),point(i+1,j),x); 
            add(point(i+1,j),point(i,j),x);
        }
    for (int i=1;i<n;i++)
        for (int j=1;j<m;j++){
            cin>>x;
            add(point(i,j),point(i+1,j+1),x);
            add(point(i+1,j+1),point(i,j),x);
        }
    cout<<Dinic();  
    return 0;
}