[bzoj1001][BeiJing2006]狼抓兔子

Description

給出一張網格，左上角點為(1,1),右下角點為(N,M).有以下三種類型的道路

1:(x,y)<==>(x+1,y)

2:(x,y)<==>(x,y+1)

3:(x,y)<==>(x+1,y+1)

截斷一條邊的代價為它的權值，求最小的代價使得從左上角不可到達右下角。

Solution

很明顯最小割就好了。

寫個dinic練練手。（好久沒寫網絡流了）

注意這裡的邊是雙向邊。

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,a) for(int i=last[a];i;i=next[i])
#define N 1000005
using namespace std;
const int inf=;
int n,m,x,l,S,T,ans,last[N],dis[N],d[N],next[N*6],v[N*6],t[N*6];
void add(int x,int y,int z) {
    t[++l]=y;v[l]=z;next[l]=last[x];last[x]=l;
    t[++l]=x;v[l]=z;next[l]=last[y];last[y]=l;
}
int get(int x,int y) {return (x-)*m+y;}
bool bfs() {
    memset(dis,,sizeof(dis));dis[S]=;
    int i=,j=;d[]=S;
    while (i<j) rep(k,d[++i]) 
        if (!dis[t[k]]&&v[k]) 
            dis[t[k]]=dis[d[i]]+,d[++j]=t[k];
    return dis[T];
}
int dinic(int x,int y) {
    if (x==T) return y;
    int now=;
    rep(i,x) if (dis[t[i]]==dis[x]+&&v[i]) {
        int k=dinic(t[i],min(y,v[i]));
        v[i]-=k;v[i^]+=k;y-=k;now+=k;
        if (!y) break;
    }
    if (!now) dis[x]=-;
    return now;
}
int main() {
    scanf("%d%d",&n,&m);S=;T=n*m;l=;
    fo(i,,n) fo(j,,m-) scanf("%d",&x),add(get(i,j),get(i,j+),x);
    fo(i,,n-) fo(j,,m) scanf("%d",&x),add(get(i,j),get(i+,j),x);
    fo(i,,n-) fo(j,,m-) scanf("%d",&x),add(get(i,j),get(i+,j+),x);
    while (bfs()) ans+=dinic(S,inf);
    printf("%d",ans);
}