Luogu2046 NOI2010 海拔 平面图、最小割、最短路

传送门

---

首先一个不知道怎么证的结论：任意点的\(H\)只会是\(0\)或\(1\)

那么可以发现原题的本质就是一个最小割，左上角为\(S\)，右下角为\(T\)，被割开的两个部分就是\(H=0\)与\(H=1\)的部分

直接上Dinic似乎有90pts

然后可以发现原图是一个经典的平面图

于是将平面图最小割转化成对偶图最短路模型，然后堆优化Dijkstra即可。

关于平面图最小割转化为对偶图最短路可以看这个

#include<bits/stdc++.h>

#define id(i , j) (((i) - 1) * N + (j))

#define INF 0x3f3f3f3f

#define st first

#define nd second

#define PII pair < int , int >

//This code is written by Itst

using namespace std;

inline int read(){

    int a = 0;

    char c = getchar();

    bool f = 0;

    while(!isdigit(c) && c != EOF){

        if(c == '-')

            f = 1;

        c = getchar();

    }

    if(c == EOF)

        exit(0);

    while(isdigit(c)){

        a = (a << 3) + (a << 1) + (c ^ '0');

        c = getchar();

    }

    return f ? -a : a;

}

const int MAXN = 255010 , MAXM = 2050010;

struct Edge{

    int end , upEd , w;

}Ed[MAXM];

int head[MAXN] , dis[MAXN];

int N , S , T , cntEd = 1;

priority_queue < PII > q;

inline void addEd(int a , int b , int c){

    Ed[++cntEd].end = b;

    Ed[cntEd].upEd = head[a];

    Ed[cntEd].w = c;

    head[a] = cntEd;

}

inline void Dijk(){

    memset(dis , 0x3f , sizeof(dis));

    dis[S] = 0;

    q.push(PII(0 , S));

    while(!q.empty()){

        PII t = q.top();

        q.pop();

        if(-t.st > dis[t.nd])

            continue;

        if(t.nd == T)

            return;

        for(int i = head[t.nd] ; i ; i = Ed[i].upEd)

            if(dis[Ed[i].end] > dis[t.nd] + Ed[i].w){

                dis[Ed[i].end] = dis[t.nd] + Ed[i].w;

                q.push(PII(-dis[Ed[i].end] , Ed[i].end));

            }

    }

}

void input(){

    N = read();

    T = id(N , N) + 1;

    for(int i = 0 ; i <= N ; ++i)

        for(int j = 1 ; j <= N ; ++j){

            int k = read();

            if(i == 0)

                addEd(S , id(i + 1 , j) , k);

            else

                if(i == N)

                    addEd(id(i , j) , T , k);

                else

                    addEd(id(i , j) , id(i + 1 , j) , k);

        }

    for(int i = 1 ; i <= N ; ++i)

        for(int j = 0 ; j <= N ; ++j){

            int k = read();

            if(j == 0)

                addEd(id(i , j + 1) , T , k);

            else

                if(j == N)

                    addEd(S , id(i , j) , k);

                else

                    addEd(id(i , j + 1) , id(i , j) , k);

        }

    for(int i = 0 ; i <= N ; ++i)

        for(int j = 1 ; j <= N ; ++j){

            int k = read();

            if(i && i != N)

                addEd(id(i + 1 , j) , id(i , j) , k);

        }

    for(int i = 1 ; i <= N ; ++i)

        for(int j = 0 ; j <= N ; ++j){

            int k = read();

            if(j && j != N)

                addEd(id(i , j) , id(i , j + 1) , k);

        }

}

void work(){

    Dijk();

    cout << dis[T];

}

int main(){

#ifndef ONLINE_JUDGE

    freopen("in" , "r" , stdin);

    //freopen("out" , "w" , stdout);

#endif

    input();

    work();

    return 0;

}