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;

}