「BZOJ2007」[NOI2010]海拔

Description

YT市是一个规划良好的城市,城市被东西向和南北向的主干道划分为n×nn\times n个区域。简单起见,可以将YT市看作 一个正方形,每一个区域也可看作一个正方形。从而,YT城市中包括(n+1)×(n+1)(n+1)\times (n+1)个交叉路口和2n×(n+1)2n\times (n+1)条双向道路(简称道路),每条双向 道路连接主干道上两个相邻的交叉路口。下图为一张YT市的地图(n=2)(n = 2),城市被划分为2×22\times 2个区域,包括3×33\times 3个交叉路口和12条双向道路。

小Z作为该市的市长,他根据统计信息得到了每天上班高峰期间YT市每条道路两个方向的人流量,即在高峰期间沿 着该方向通过这条道路的人数。每一个交叉路口都有不同的海拔高度值,YT市市民认为爬坡是一件非常累的事情,每向上爬h的高度,就需要消耗hh的体力。如果 是下坡的话,则不需要耗费体力。因此如果一段道路的终点海拔减去起点海拔的值为hh(注意h可能是负数),那么一个人经过这段路所消耗的体力是max{0,h}\max\{0, h\}(这里max{a,b}\max\{a, b\}表示取a,ba, b两个值中的较大值)。
小Z还测量得到这个城市西北角的交叉路口海拔为00,东南角的交叉路口海拔为11(如上图所示),但其它交叉路口的海拔高度都无法得知。小Z想知道在最理想的情况下(即你可以任意假设其他路口的海拔高度),每天上班高峰期间所有人爬坡消耗的总体力和的最小值。

Input

第一行包含一个整数nn,含义如上文所示。接下来4n(n+1)4n(n + 1)行,每行包含一个非负整数分别表示每一条道路每一个
方向的人流量信息。
输入顺序:(n+1)n(n + 1)n个数表示所有从西到东方向的人流量,然后n(n+1)n(n + 1)个数表示所有从北到南方向的人流量,(n+1)n(n + 1)n个数表示所有从东到西方向的人流量,最后是n(n+1)n(n + 1)个数表示所有从南到北方向的人流量。
对于每一个方向,输入顺序按照起点由北向南,若南北方向相同时由西到东的顺序给出(参见样例输入)。

Output

仅包含一个数,表示在最理想情况下每天上班高峰期间所有人爬坡所消耗的总体力和(即总体力和的最小值),结
果四舍五入到整数。

Sample Input

1
2
3
4
5
6
7
8
9
1
1
2
3
4
5
6
7
8

Sample Output

1
3

HINT


对于20%20\%的数据:n3n \leq 3
对于50%50\%的数据:n15n \leq 15
对于80%80\%的数据:n40n \leq 40
对于100%100\%的数据:1n5001 \leq n \leq 50000 \leq 流量 1000000\leq 1000000且所有流量均为整数。

Solution


只有左上角是00和右下角是11,贪心的话就是左上角全是00,右下角都是11,现在就是要求左上角和右下角的分界线的最小长度,也就是求最小割。最小割等于最大流,可以转对偶图用求最短路来做。
是有向边,直接倒过来建边就行了。至于为什么,画个图模拟一下就知道了。相当于原本是往右下角走,但是倒过来就是从右下角到左上角,如果最小割经过了反向的边,那么就相当于最小割集是来回走的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#include<queue>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 600 * 600, M = N * 6;
int n;
int s, t;
struct Edge {
int u, v, nxt, w;
}e[M*2];
int head[N], en;
void addedge(int x, int y, int z) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en;
e[en].w = z;
}
int d[N];
bool vis[N];
priority_queue<pii, vector<pii>, greater<pii> >q;
int dijkstra() {
memset(d, 0x3f, sizeof d);
d[s] = 0;
q.push(mk(0, s));
while(!q.empty()) {
pii now = q.top(); q.pop();
int x = now.nd;
if(vis[x]) continue;
vis[x] = 1;
for(int i = head[x]; i; i = e[i].nxt) {
int y = e[i].v;
if(d[y] > d[x] + e[i].w) {
d[y] = d[x] + e[i].w;
q.push(mk(d[y], y));
}
}
}
return d[t];
}
int main() {
n = read();
s = n * n + 1;
t = n * n + 2;
for(int i = 1; i <= n + 1; ++i) { //西->东
for(int j = 1; j <= n; ++j) {
int x = read();
if(i == 1) {
addedge(j, t , x);
} else if(i == n + 1) {
addedge(s, (n - 1) * n + j, x);
} else addedge((i - 1) * n + j, (i - 2) * n + j, x);
}
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n + 1; ++j) { //北->南
int x = read();
if(j == 1) addedge(s, (i - 1) * n + j, x);
else if(j == n + 1) addedge(i * n, t, x);
else addedge((i - 1) * n + j - 1, (i - 1) * n + j, x);
}
}
for(int i = 1; i <= n + 1; ++i) { //东->西
for(int j = 1; j <= n; ++j) {
int x = read();
if(i == 1) addedge(t, j, x);
else if(i == n + 1) addedge((n - 1) * n + j, s, x);
else addedge((i - 2) * n + j, (i - 1) * n + j, x);
}
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n + 1; ++j) { //南->北
int x = read();
if(j == 1) addedge((i - 1) * n + j,s , x);
else if(j == n + 1) addedge(t, i * n, x);
else addedge((i - 1) * n + j, (i - 1) * n + j - 1, x);
}
}
writeln(dijkstra());
return 0;
}