链接：bzoj2007
思路
经过思考可以发现2个结论：
- 选0/1外的值作为海拔没有必要
- 小于0的值改为0，大于1的值改为1，答案不会更差。
- 对(0, 1)之间的值，不如选0/1更优。
- 海拔为0/1的分别只有一个连通块
- 如果1有≥2个连通块，把不包含(n, n)的连通块拍扁，答案不会更差。
然后就转化为了平面图最小割。
注意一点：最小割是可以绕圈子的！所以不能忽略从南到北、从东到西的边！
举个栗子：
遇到平面图最小割问题的时候，可以想象割边集合从超级源点 $s$ “生长”到超级汇点 $t$ . 在割左手边的是 $\mathbb{S}$ 集合，在其右手边的是 $\mathbb{T}$ 集合。根据这点，就可以决定对偶图边有向与否，取何方向。一般地，把原来的有向边逆时针旋转 $90^{\circ}$ ，即为其在对偶图中的方向。
还有就是要用 Dijkstra，因为网格图卡 SPFA ……
代码
#include <bits/stdc++.h>
#define fst first
#define scd second
#define mp make_pair
#define rep(i, x) for(int i = 1; i <= (x); i++)
using namespace std;
typedef pair<int, int> HeapNode;
struct Edge { int v, len, next; };
const int MAXN = 3e5, MAXM = 2e6;
int n, s, t, e_ptr = 1, dist[MAXN+10], head[MAXN+10]; Edge E[(MAXM+10)<<1];
inline int idx(int i, int j) { return (i-1) * n + j; }
inline bool valid(int i, int j) { return i >= 1 && i <= n && j >= 1 && j <= n; }
inline void AddEdge(int u, int v, int len) {
E[++e_ptr] = (Edge) { v, len, head[u] }; head[u] = e_ptr;
}
int Dijkstra() {
priority_queue<HeapNode, vector<HeapNode>, greater<HeapNode> > pq;
memset(dist, 0x3f, sizeof(dist));
dist[s] = 0; pq.push(mp(dist[s], s));
while(!pq.empty()) {
HeapNode p = pq.top(); pq.pop();
int u = p.scd;
if(dist[u] != p.fst) continue;
for(int j=head[u]; j; j=E[j].next) {
int v = E[j].v, len = E[j].len;
if(dist[v] > dist[u] + len) {
dist[v] = dist[u] + len;
pq.push(mp(dist[v], v));
}
}
}
return dist[t];
}
inline int readint() {
int f=1, r=0; char c=getchar();
while(!isdigit(c)) { if(c=='-')f=-1; c=getchar(); }
while(isdigit(c)) { r=r*10+c-'0'; c=getchar(); }
return f*r;
}
void Init() {
n = readint(); s = MAXN - 1; t = MAXN;
rep(i, n+1) rep(j, n) {
int x = readint();
if(i == 1)
AddEdge(idx(i, j), t, x);
else if(i == n+1)
AddEdge(s, idx(i-1, j), x);
else
AddEdge(idx(i, j), idx(i-1, j), x);
}
rep(i, n) rep(j, n+1) {
int x = readint();
if(j == 1)
AddEdge(s, idx(i, j), x);
else if(j == n+1)
AddEdge(idx(i, j-1), t, x);
else
AddEdge(idx(i, j-1), idx(i, j), x);
}
rep(i, n+1) rep(j, n) {
int x = readint();
if(i == 1)
AddEdge(t, idx(i, j), x);
else if(i == n+1)
AddEdge(idx(i-1, j), s, x);
else
AddEdge(idx(i-1, j), idx(i, j), x);
}
rep(i, n) rep(j, n+1) {
int x = readint();
if(j == 1)
AddEdge(idx(i, j), s, x);
else if(j == n+1)
AddEdge(t, idx(i, j-1), x);
else
AddEdge(idx(i, j), idx(i, j-1), x);
}
}
void Work() {
cout << Dijkstra();
}
int main() {
Init(); Work();
return 0;
}
