[BZOJ 2007][NOI 2010] 海拔

题目大意

有一个 $n \times m$ 的网格,网格顶点是城市,同时有一个海拔(不一定是整数),左上角的海拔为 $0$,右下角为 $1$,海拔各不相等。给定两点间的流量(路的两个方向流量不一定相同),若海拔上升,则消耗体力为 流量 $\times$ 海拔差。求最小的体力消耗,答案四舍五入为整数。

$1 \leqslant n ,\; m \leqslant 500$

$1 \leqslant w \leqslant 1,000,000$ (流量)

题目链接

BZOJ 2007

CodeVS 1940

题解

虽然要求海拔各不相同,但海拔不一定为整数 + 答案四舍五入,所以这个要求无影响。答案显然是把网格分为左上角的一块 $0$ 和右下角的一块 $1$,显然是最小割,但是会 TLE(据说)。

考虑到图是平面图,可以建对偶图跑最短路,相当于把所有的边顺/逆时针转 $90^{\circ} $。

一开始搞错了边的读入顺序,WA 了两遍。它的边,无论是横向边还是纵向边,都是先从左到右,后从上到下给出的

代码

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
#include <cstdio>
#include <climits>
#include <queue>
#include <algorithm>
// #define DBG
const int MAXN = 505;
struct Edge;
struct Node {
Edge *e;
int dist;
bool vis;
} N[MAXN * MAXN];
struct Edge {
Node *u, *v;
Edge *next;
int w;
Edge(Node *u, Node *v, int w) : u(u), v(v), w(w), next(u->e) {}
};
void addEdge(int u, int v, int w) {
#ifdef DBG
printf("edge : %d --> %d, w = %d\n", u, v, w);
#endif
N[u].e = new Edge(&N[u], &N[v], w);
}
namespace Dijkstra {
struct HeapNode {
Node *u;
int dist;
bool operator<(const HeapNode &another) const {
return dist > another.dist;
}
};
void solve(Node *s, int n) {
for (int i = 0; i < n; i++) N[i].dist = INT_MAX, N[i].vis = false;
s->dist = 0;
std::priority_queue<HeapNode> q;
q.push((HeapNode) {s, 0});
while (!q.empty()) {
Node *u = q.top().u;
q.pop();
if (u->vis) continue;
u->vis = true;
for (Edge *e = u->e; e; e = e->next) {
if (e->v->dist > u->dist + e->w) {
e->v->dist = u->dist + e->w;
q.push((HeapNode) {e->v, e->v->dist});
}
}
}
}
}
int main() {
int n;
scanf("%d", &n);
const int s = 0, t = n * n + 1;
for (int i = 0; i <= n; i++) for (int j = 1; j <= n; j++) {
int x;
scanf("%d", &x);
addEdge(i ? (i - 1) * n + j : s, i != n ? i * n + j : t, x);
}
for (int i = 1; i <= n; i++) for (int j = 0; j <= n; j++) {
int x;
scanf("%d", &x);
addEdge(j != n ? (i - 1) * n + j + 1 : s, j ? (i - 1) * n + j : t, x);
}
for (int i = 0; i <= n; i++) for (int j = 1; j <= n; j++) {
int x;
scanf("%d", &x);
addEdge(i != n ? i * n + j : t, i ? (i - 1) * n + j : s, x);
}
for (int i = 1; i <= n; i++) for (int j = 0; j <= n; j++) {
int x;
scanf("%d", &x);
addEdge(j ? (i - 1) * n + j : t, j != n ? (i - 1) * n + j + 1 : s, x);
}
Dijkstra::solve(&N[s], t + 1);
printf("%d\n", N[t].dist);
return 0;
}