「NOI2010」海拔 - 平面图最小割

题目大意

---

题目分析

不难发现，高度只可能是$0,1$。
证明：若高度$\gt 1$，将其修改为$1$一定不会变差，若高度是实数，在人流量更少的结点一次性将高度修改为$1$一定不会变差。
不难发现，高度为$0$与$1$的结点构成两个连通块。
证明：若有第三个连通块被一个高度不同的连通块所包含，那么将其高度替换为外连通块的高度答案一定不会变差。

这样我们就可以用最小割解决问题了。（$0$与$1$的分界线边权和即为答案）

Howerver，我无比优美的Dinic被卡了（$90pt$TLE），用平面图转对偶图解决问题（愿意写预流推进那当然可以）。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=250005;

struct Edge {
	int from,to,dist;
	Edge(int x=0,int y=0,int d=0):from(x),to(y),dist(d) {}
};

int n,dist[maxn],id[505][505];
bool vst[maxn];
vector<Edge>edges[maxn];

void AddEdge(int x,int y,int v) {
	edges[x].push_back(Edge(x,y,v));
}

struct HeapNode {
	int d,u;
	bool operator < (const HeapNode& b) const {
		return d>b.d;
	} 
};

void Dijkstra(int s) {
	priority_queue<HeapNode>Q;
	for(int i=1; i<=n*n+2; i++)dist[i]=INT_MAX;
	Q.push((HeapNode) {0,s});
	dist[s]=0;
	while(!Q.empty()) {
		int Now=Q.top().u;
		Q.pop();
		if(vst[Now])continue;
		vst[Now]=1;
		for(Edge& e:edges[Now]) {
			int Next=e.to;
			if(dist[Next]>dist[Now]+e.dist) {
				dist[Next]=dist[Now]+e.dist;
				Q.push((HeapNode) {dist[Next],Next});
			}
		}
	}
}

int main() {
	n=Get_Int();
	int S=n*n+1,T=n*n+2;
	for(int i=1; i<=n; i++)id[n+1][i]=id[i][0]=S;
	for(int i=1; i<=n; i++)id[0][i]=id[i][n+1]=T;
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			id[i][j]=(i-1)*n+j;
	for(int i=1; i<=n+1; i++)
		for(int j=1; j<=n; j++)
			AddEdge(id[i][j],id[i-1][j],Get_Int());
	for(int i=1; i<=n; i++)
		for(int j=0; j<=n; j++)
			AddEdge(id[i][j],id[i][j+1],Get_Int());
	for(int i=0; i<=n; i++)
		for(int j=1; j<=n; j++)
			AddEdge(id[i][j],id[i+1][j],Get_Int());
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n+1; j++)
			AddEdge(id[i][j],id[i][j-1],Get_Int());
	Dijkstra(S);
	printf("%d\n",dist[T]);
	return 0;
}