luogu2046[NOI2010]海拔 对偶图优化

链接

https://www.luogu.org/problemnew/show/P2046

思路

海拔一定是0或者1，而且会有一条01交错的分界线。
转化为最小割，用对偶图优化求得。最小割论文写的特清楚。

代码

#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=2e6+7,inf=0x3f3f3f3f;
int read() {
    int x=0,f=1;char s=getchar();
    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
    return x*f;
}
int n,m,S,T;
struct edge {
    int v,nxt,q;
}e[N*5];
int head[N*5],tot;
void add(int u,int v,int q) {
    // cout<<u<<" "<<v<<"\n";
    e[++tot].v=v;
    e[tot].q=q;
    e[tot].nxt=head[u];
    head[u]=tot;
}
struct node {
    int x,y;
    bool operator < (const node &b) const {
        return x>b.x;
    }
};
priority_queue<node> q;
int dis[N];
void dij() {
    memset(dis,0x3f,sizeof(dis));
    q.push((node){0,S});
    dis[S]=0;
    while(!q.empty()) {
        node u=q.top();
        q.pop();
        if(u.x!=dis[u.y]) continue;
//      cout<<head[S]<<" "<<<<"\n";
        for(int i=head[u.y];i;i=e[i].nxt) {
            int v=e[i].v;
//          cout<<u.y<<" -> "<<v<<" "<<e[i].q<<"\n";
            if(dis[v]>dis[u.y]+e[i].q) {
                dis[v]=dis[u.y]+e[i].q;
                q.push((node){dis[v],v});
            }
        }   
    }
}
int main() {
    // freopen("testdata.in","r",stdin);
    n=read();
    S=n*n*2+1,T=n*n*2+2;
    for(int i=1,x,TX,TY;i<=n+1;++i) {
        for(int j=1;j<=n;++j) {
            x=read();
            TX=(i-1)*n+j-n,TY=(i-1)*n+j;
            if(i==1) TX=S;
            if(i==n+1) TY=T;
            add(TX,TY,x);
        }
    }
    for(int i=1,x,TX,TY;i<=n;++i) {
        for(int j=1;j<=n+1;++j) {
            x=read();
            TX=(i-1)*n+j-1,TY=(i-1)*n+j;
            if(j==1) TX=T;
            if(j==n+1) TY=S;
            add(TY,TX,x);
        }
    }
    for(int i=1,x,TX,TY;i<=n+1;++i) {
        for(int j=1;j<=n;++j) {
            x=read();
            TX=(i-1)*n+j-n,TY=(i-1)*n+j;
            if(i==1) TX=S;
            if(i==n+1) TY=T;
            swap(TX,TY);
            add(TX,TY,x);
        }
    }
    for(int i=1,x,TX,TY;i<=n;++i) {
        for(int j=1;j<=n+1;++j) {
            x=read();
            TX=(i-1)*n+j-1,TY=(i-1)*n+j;
            if(j==1) TX=T;
            if(j==n+1) TY=S;
            swap(TX,TY);
            add(TY,TX,x);
        }
    }
    dij();
    printf("%d\n",dis[T]);
    return 0;
}