BZOJ2007 [Noi2010]海拔（洛谷P2046）平面圖最小割->對偶圖最短路

平面圖最小割->對偶圖最短路

BZOJ題目傳送門

洛谷題目傳送門

最理想的情況當然是在某邊道路上海拔從0變成1，而其它的海拔不變。這樣總體力和就是這些邊的權值和。

把權值看成容量的話就轉變成一個最小割的問題。因為是平面圖，可以轉成對偶圖的最短路來做。

順便學了一發Dij+Heap。

其實挺套路的。主要建圖很傷腦筋。我是右上為 S S ，左下為TT。

代碼：

#include<queue>
#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 505
#define M N*N
#define F inline
using namespace std;
struct edge{ int nxt,to,d; }ed[M<<];
struct P{ int x,d; };
int n,m,k,s,t,h[M],d[M];
priority_queue <P> q;
F char readc(){
    static char buf[],*l=buf,*r=buf;
    if (l==r) r=(l=buf)+fread(buf,,,stdin);
    return l==r?EOF:*l++;
}
F int _read(){
    int x=; char ch=readc();
    while (!isdigit(ch)) ch=readc();
    while (isdigit(ch)) x=(x<<)+(x<<)+(ch^),ch=readc();
    return x;
}
#define addedge(x,y,z) ed[++k]=(edge){h[x],y,z},h[x]=k
F bool operator < (P a,P b){ return a.d>b.d; }
F int Dij(){
    for (int i=;i<=t;i++) d[i]=;
    q.push((P){s,});
    while (!q.empty()){
        if (q.top().d>d[q.top().x]) { q.pop(); continue; } 
        int x=q.top().x; q.pop();
        for (int i=h[x],v;i;i=ed[i].nxt)
            if (d[x]+ed[i].d<d[v=ed[i].to])
                d[v]=d[x]+ed[i].d,q.push((P){v,d[v]});
    }
    return d[t];
}
int main(){
    n=_read(),t=n*n+;
    for (int i=;i<=n;i++)
        for (int j=;j<=n;j++)
            addedge(max(s,(i-)*n+j),min(t,i*n+j),_read());
    for (int i=;i<=n;i++)
        for (int j=;j<=n;j++)
            if (!j) addedge((i-)*n+,t,_read());
            else if (j==n) addedge(s,i*n,_read());
            else addedge((i-)*n+j+,(i-)*n+j,_read());
    for (int i=;i<=n;i++)
        for (int j=;j<=n;j++)
            addedge(min(t,i*n+j),max(s,(i-)*n+j),_read());
    for (int i=;i<=n;i++)
        for (int j=;j<=n;j++)
            if (!j) addedge(t,(i-)*n+,_read());
            else if (j==n) addedge(i*n,s,_read());
            else addedge((i-)*n+j,(i-)*n+j+,_read());
    return printf("%d\n",Dij()),;
}