【BZOJ】2007: [Noi2010]海拔（平面图转对偶图）

题目

传送门：QWQ

分析

左上角是0，右下角是1。那么大概整张图是由0 1构成的。

那么我们要找到0和1的分界线，值就是最小割。

然后变成求原图最小割。

考虑到此题是平面图，那么就转成对偶图跑最短路。

完了。

总结：以后看到数据在$ nlog(n) $范围内的题，给的图是方格图，给的边还方方正正，那么多半是平面图转对偶图。

代码

#include <bits/stdc++.h>

using namespace std;

const int maxn=*;

vector<int> G[maxn];

struct Edge{ int u,v,dis; };

vector<Edge> edges;

struct HeapNode{

    int x,dis;

    bool operator <(const HeapNode& a) const{ return dis>a.dis; }

};

void link(int u,int v,int dis){

    edges.push_back((Edge){u,v,dis}); //edges.push_back((Edge){v,u,dis});

    int m=edges.size(); G[u].push_back(m-);

}

int d[maxn],vis[maxn];

priority_queue<HeapNode> que;

int dijkstra(int s,int t){

    memset(d,,sizeof(d));

    d[s]=; que.push((HeapNode){s,}); //vis[s]=1;

    while(!que.empty()){

        HeapNode x=que.top(); que.pop();

        if(vis[x.x]) continue; vis[x.x]=;

        int u=x.x;

        for(int i=;i<G[u].size();i++){

            Edge& e=edges[G[u][i]];

            if(d[e.v]>d[u]+e.dis){

                d[e.v]=d[u]+e.dis;

                que.push((HeapNode){e.v,d[e.v]});

            }

        }

    }

    return d[t];

}

int num[][];

int main(){

    int n,x;scanf("%d",&n);

    int    s =  , t = n * n + ;

    for(int i =  ; i <= n ; i ++ )

        num[][i] = num[i][n + ] = s , num[i][] = num[n + ][i] = t;

    for(int i=; i <= n ; i ++ )

        for(int j =  ; j <= n ; j ++ )

            num[i][j] = n * (i - ) + j;

    for(int i=;i<=n;i++) for(int j=;j<=n;j++) scanf("%d",&x),link(num[i][j] , num[i+][j] , x);

    for(int i=;i<=n;i++) for(int j=;j<=n;j++) scanf("%d",&x),link(num[i][j+] , num[i][j] , x);

    for(int i=;i<=n;i++) for(int j=;j<=n;j++) scanf("%d",&x),link(num[i+][j] , num[i][j] , x);

    for(int i=;i<=n;i++) for(int j=;j<=n;j++) scanf("%d",&x),link(num[i][j] , num[i][j+] , x);

    printf("%d\n",dijkstra(s,t));

    return ;

}