BZOJ 2007
LUOGU 2046
Description
YT市是一个规划良好的城市，城市被东西向和南北向的主干道划分为n×n个区域。简单起见，可以将YT市看作一个正方形，每一个区域也可看作一个正方形。从而，YT城市中包括(n+1)×(n+1)个交叉路口和2n×(n+1)条双向道路（简称道路），每条双向道路连接主干道上两个相邻的交叉路口。下图为一张YT市的地图(n = 2)，城市被划分为2×2个区域，包括3×3个交叉路口和12条双向道路。
小Z作为该市的市长，他根据统计信息得到了每天上班高峰期间YT市每条道路两个方向的人流量，即在高峰期间沿着该方向通过这条道路的人数。每一个交叉路口都有不同的海拔高度值，YT市市民认为爬坡是一件非常累的事情，每向上爬h的高度，就需要消耗h的体力。如果是下坡的话，则不需要耗费体力。因此如果一段道路的终点海拔减去起点海拔的值为h(注意h可能是负数)，那么一个人经过这段路所消耗的体力是max{0, h}（这里max{a, b}表示取a, b两个值中的较大值）。 小Z还测量得到这个城市西北角的交叉路口海拔为0，东南角的交叉路口海拔为1(如上图所示)，但其它交叉路口的海拔高度都无法得知。小Z想知道在最理想的情况下（即你可以任意假设其他路口的海拔高度），每天上班高峰期间所有人爬坡所消耗的总体力和的最小值。
Input
第一行包含一个整数n，含义如上文所示。接下来4n(n + 1)行，每行包含一个非负整数分别表示每一条道路每一个方向的人流量信息。输入顺序：n(n + 1)个数表示所有从西到东方向的人流量，然后n(n + 1)个数表示所有从北到南方向的人流量，n(n + 1)个数表示所有从东到西方向的人流量，最后是n(n + 1)个数表示所有从南到北方向的人流量。对于每一个方向，输入顺序按照起点由北向南，若南北方向相同时由西到东的顺序给出(参见样例输入)。
Output
仅包含一个数，表示在最理想情况下每天上班高峰期间所有人爬坡所消耗的总体力和（即总体力和的最小值），结果四舍五入到整数。
Sample Input
1
1
2
3
4
5
6
7
8
Sample Output
3
HINT
对于20%的数据：n ≤ 3；
对于50%的数据：n ≤ 15；
对于80%的数据：n ≤ 40；
对于100%的数据：1 ≤ n ≤ 500，0 ≤ 流量 ≤ 1,000,000且所有流量均为整数。
放在任务计划中几天了，知道昨天才和 \(Chdy\) 讨论出了个结果。
首先根据题意，可以分析出
于是我们可以假设：如果全图的海拔都为 0 ，那么费用就永远为 0 了。但是汇点的海拔为 1 ，这就说明是会有一些边是从海拔 0 的点走到海拔 1 的地方的。所以整张图就变成了左上角全为 0 ，右下角全为 1 的了。
那答案费用就是那些分界线的费用了，也就是最小割了。
然后我们（其实还是 \(Chdy\)）提出：反向边到底有用没？
由于我们想到的分界线是直线，所以怎么想，反向边都没用，额...直到看到了这个帖子：40分的同学看这里。
原来最小割还能转圈圈。
然后发现数据是 \(500*500\)，网络流要被卡爆了，我们便翻了题解看看上述思路是否正确，以及正解到底是什么。
最后得出的结论：这道题是狼抓兔子的加强版，正解就是平面图转对偶图跑最短路了。
为了写这个题，我只好去现学一波平面图转对偶图。附上平面图的一个重要定理。
平面图 \(G\) 的所有面的度之和等于其边数 \(|E|\) 的 \(2\) 倍：\[\sum deg(R_i)=\left|E\right|*2\]
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int maxn=510,maxm=maxn*maxn*4,inf=0x3f3f3f3f;
char buf[1<<15],*fs,*ft;
inline char getc() { return (ft==fs&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),ft==fs))?0:*fs++; }
template<typename T>inline void read(T &x)
{
x=0;
T f=1, ch=getchar();
while (!isdigit(ch) && ch^'-') ch=getchar();
if (ch=='-') f=-1, ch=getchar();
while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar();
x*=f;
}
template<typename T>inline void write(T x)
{
if (!x) { putchar('0'); return ; }
if (x<0) putchar('-'), x=-x;
T num=0, ch[20];
while (x) ch[++num]=x%10+48, x/=10;
while (num) putchar(ch[num--]);
}
int ver[maxm],edge[maxm],Next[maxm],head[maxn*maxn],len=1;
inline void add(int x,int y,int z)
{
ver[++len]=y,edge[len]=z,Next[len]=head[x],head[x]=len;
}
int s,t;
int dist[maxn*maxn];
bool vis[maxn*maxn];
inline void Dijkstra()
{
priority_queue<pii,vector<pii>,greater<pii> >q;
memset(dist,0x3f,sizeof(dist));
q.push(make_pair(0,s)),dist[s]=0;
while (!q.empty())
{
int x=q.top().second;
q.pop();
if (vis[x]) continue;
vis[x]=1;
for (int i=head[x]; i; i=Next[i])
{
int y=ver[i],z=edge[i];
if (dist[y]>dist[x]+z)
{
dist[y]=dist[x]+z;
q.push(make_pair(dist[y],y));
}
}
}
}
int n;
inline int hash(int i,int j)
{
return (i-1)*n+j;
}
int main()
{
read(n);
s=0,t=n*n+1;
for (int i=0; i<=n; ++i)
for (int j=1,x; j<=n; ++j)
{
read(x);
if (!i) add(hash(i+1,j),t,x);
else if (i==n) add(s,hash(i,j),x);
else add(hash(i+1,j),hash(i,j),x);
}
for (int i=1; i<=n; ++i)
for (int j=0,x; j<=n; ++j)
{
read(x);
if (!j) add(s,hash(i,j+1),x);
else if (j==n) add(hash(i,j),t,x);
else add(hash(i,j),hash(i,j+1),x);
}
for (int i=0; i<=n; ++i)
for (int j=1,x; j<=n; ++j)
{
read(x);
if (!i) add(t,hash(i+1,j),x);
else if (i==n) add(hash(i,j),s,x);
else add(hash(i,j),hash(i+1,j),x);
}
for (int i=1; i<=n; ++i)
for (int j=0,x; j<=n; ++j)
{
read(x);
if (!j) add(hash(i,j+1),s,x);
else if (j==n) add(t,hash(i,j),x);
else add(hash(i,j+1),hash(i,j),x);
}
Dijkstra();
write(dist[t]);
return 0;
}BZOJ 2007: [Noi2010]海拔 平面图转对偶图最短路
原文：https://www.cnblogs.com/G-hsm/p/11328995.html