题目大意

有一个N\times M大小的“网格图”(如下图所示,N\leq 1000,M\leq 1000),设左上角为原点,右下角为汇点,每条边的边权为割断这条边的代价,求该图将源点和汇点割到不连通的最小代价,图是无向图
转自BZOJ

算法讲解

割的定义:想象一个有向图,源点s汇点t。如果你割断(去掉)了一些边,使从st不再联通,那么这些边构成一个割集
割的大小:定义有向边的边权为这条边的容量,那么一个割的大小等于割集中的边的容量之和
最大流最小割定理:一个图的最小割等于从s到t的最大流


考虑从性感感性层面证明一下这个定理。
首先,由于这个割把原图中的点分成了互不连通的两个集合,定义集合S为所有和源点连通的点,集合T为所有和汇点连通的点。即设两点间流量f容量c,则有

    \[f(s,u)<c(s,u) ,u\in S\ f(v,t)<c(v,t) ,v\in T.\]

那么这个割的大小,是一定不小于从ST流量的。因为割的大小为从ST容量,而流量不一定要流满这些边的所有容量。即设该割的流量F大小(容量)C,则有

    \[F(s,t)\leq C(s,t).\]

那么因为割有下界,流也就有上界。并且最小割等于最大流
这个最小割显然存在,当流最大的时候,不存在一条增广路使st连通,这就自然形成了一个割。而这个情况下我们割掉的边,都是剩余容量为零的边(在残量网络中的断边),这些边的流量等于容量,我们割掉这些边后,割的大小恰好等于流的大小,即此时

    \[F(s,t)=C(s,t).\]


这道题就是求无向图的最小割,边数有点多,总共1000\times 1000\times 3大约3e6条。故在跑网络流的时候需要一些玄学优化,用到了当前弧优化多路增广
当前弧优化就是在dfs的时候随时更新每个点的出边的链首,这样在下一次遍历到这个点的时候可以直接从容量不为零的第一条边开始枚举。

代码

#include<bits/stdc++.h>
#define OnlineJudge
#define INF 1000000000
#define N 1100000
#define W(x,y) ((x)*m+(y))
using namespace std;
int rd(){
    int x=0,y=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-')
            y=-y;
        c=getchar();
    }
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return x*y;
}
struct node{
    int tar,to,nxt;
}table[N<<3];
int head[N],cur[N],tot=2,n,m;
void ins(int x,int y,int z){
    table[tot].to=y;
    table[tot].tar=z;
    table[tot].nxt=head[x];
    head[x]=tot++;
}
void input(){
    #ifndef OnlineJudge
    freopen("in.txt","r",stdin);
    #endif
    register int t;
    n=rd();m=rd();
    for(int i=0;i<n;i++)
        for(int j=0;j<m-1;j++){
            ins(W(i,j),W(i,j+1),t=rd());
            ins(W(i,j+1),W(i,j),t);
        }
    for(int i=0;i<n-1;i++)
        for(int j=0;j<m;j++){
            ins(W(i,j),W(i+1,j),t=rd());
            ins(W(i+1,j),W(i,j),t);
        }
    for(int i=0;i<n-1;i++)
        for(int j=0;j<m-1;j++){
            ins(W(i,j),W(i+1,j+1),t=rd());
            ins(W(i+1,j+1),W(i,j),t);
        }
    return;
}
queue<int>Q;
int num[N];
bool bfs(){
    memset(num,0,sizeof num);
    Q.push(0);num[0]=1;
    while(!Q.empty()){
        int x=Q.front();Q.pop();
        for(int i=head[x];i;i=table[i].nxt){
            int t=table[i].to;
            if(table[i].tar&&num[t]==0){
                Q.push(t);
                num[t]=num[x]+1;
            }
        }
    }
    for(int i=0;i<=W(n-1,m-1);i++)
        cur[i]=head[i];
    return num[W(n-1,m-1)]!=0;
}
int dfs(int x,int instr){
    if(x==W(n-1,m-1)){
        return instr;
    }
    int outstr=0;
    for(int &i=cur[x];i;i=table[i].nxt){
        int to=table[i].to;
        if(table[i].tar&&num[to]==num[x]+1){
            int stream=dfs(to,min(instr,table[i].tar));
            table[i].tar-=stream;
            table[i^1].tar+=stream;
            instr-=stream;
            outstr+=stream;
            #ifndef OnlineJudge
            if(stream!=0){printf("%d %d %d\n",x,to,stream);if(x==0)printf("\n");}
            #endif
        }
        if(instr==0)break;
    }
    return outstr;
}
int main(){
    int ans=0;
    input();
    while(bfs()){
        ans+=dfs(0,INF);
    }
    printf("%d\n",ans);
}


血まみれからの方がさ,勝つ時にはカッコイイだろう.