[NOI2010]海拔

Posted by Panda2134's Blog on March 6, 2018

链接:bzoj2007

思路

​ 经过思考可以发现2个结论:

  1. 选0/1外的值作为海拔没有必要
    • 小于0的值改为0,大于1的值改为1,答案不会更差。
    • 对(0, 1)之间的值,不如选0/1更优。
  2. 海拔为0/1的分别只有一个连通块
    • 如果1有≥2个连通块,把不包含(n, n)的连通块拍扁,答案不会更差。

然后就转化为了平面图最小割。

注意一点:最小割是可以绕圈子的!所以不能忽略从南到北、从东到西的边!

举个栗子:

Altitude

​ 遇到平面图最小割问题的时候,可以想象割边集合从超级源点 $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;
}