BZOJ2007/LG2046 「NOI2010」海拔平面图最小割转对偶图最短路

问题描述

BZOJ2007

LG2046

题解

发现左上角海拔为 \(0\) ，右上角海拔为 \(1\) 。

上坡要付出代价，下坡没有收益，所以有坡度的路越少越好。

所以海拔为 \(1\) 的点，和海拔为 \(0\) 的点，一定能够在这个网格图中由一条连续的线划分为两个集合。

将一个图中的所有结点划分为两个集合，显然为最小割模型。

又发现是网格图，所以平面图最小割转化为对偶图最短路。

\(\mathrm{Code}\)

不删调试见祖宗

#include<bits/stdc++.h>

using namespace std;

const int maxn=500*500+3;

int n,S,T;

int Head[maxn],to[maxn*5],Next[maxn*5],w[maxn*5],tot=1;

int fr[maxn*5];

void add(int x,int y,int z){

	fr[++tot]=y,to[tot]=x,Next[tot]=Head[y],Head[y]=tot,w[tot]=z;

}

int id(int x,int y){

	return (x-1)*n+y;

}

void Init(void){

	scanf("%d",&n);

}

void WestToEast(void){

	for(int i=1,x;i<=n;i++){

		scanf("%d",&x);

		add(id(1,i),S,x);

	}

	for(int i=2;i<=n;i++){

		for(int j=1,x;j<=n;j++){

			scanf("%d",&x);

			add(id(i,j),id(i-1,j),x);

		}

	}

	for(int i=1,x;i<=n;i++){

		scanf("%d",&x);

		add(T,id(n,i),x);

	}

}

void NorthToSouth(void){

	for(int i=1,x;i<=n;i++){

		scanf("%d",&x);

		add(T,id(i,1),x);

		for(int j=2;j<=n;j++){

			scanf("%d",&x);

			add(id(i,j-1),id(i,j),x);

		}

		scanf("%d",&x);

		add(id(i,n),S,x);

	}

}

void EastToWest(void){

	for(int i=1,x;i<=n;i++){

		scanf("%d",&x);

		add(S,id(1,i),x);

	}

	for(int i=2;i<=n;i++){

		for(int j=1,x;j<=n;j++){

			scanf("%d",&x);

			add(id(i-1,j),id(i,j),x);

		}

	}

	for(int i=1,x;i<=n;i++){

		scanf("%d",&x);

		add(id(n,i),T,x);

	}

}

//n lines

//n+1 every-line

void SouthToNorth(void){

	for(int i=1,x;i<=n;i++){

		scanf("%d",&x);

		add(id(i,1),T,x);

		for(int j=2;j<=n;j++){

			scanf("%d",&x);

			add(id(i,j),id(i,j-1),x);

		}

		scanf("%d",&x);

		add(S,id(i,n),x);

	}

}

void debug(){

	printf("\n### S = %d\n",S);

	printf("### T = %d\n\n",T);

	for(int i=2;i<=tot;i++){

		printf("*** From %d To %d , val = %d\n",fr[i],to[i],w[i]);

	}

}

void Graph_build(void){

	S=n*n+1,T=S+1;

	WestToEast();

	NorthToSouth();

	EastToWest();

	SouthToNorth();

}

int dis[maxn];

bool vis[maxn];

#define pii(x,y) make_pair(x,y)

void dijkstra(void){

	memset(dis,0x3f,sizeof(dis));

	priority_queue<pair<int,int> >q;

	q.push(pii(0,S));dis[S]=0;

	while(!q.empty()){

		int x=q.top().second;q.pop();

		if(vis[x]) continue;vis[x]=1;

		if(x==T) return;

		for(int i=Head[x];i;i=Next[i]){

			int y=to[i];

			if(dis[y]>dis[x]+w[i]){

				dis[y]=dis[x]+w[i];

				q.push(pii(-dis[y],y));

			}

		}

	}

}

void Work(void){

	Graph_build();

	#ifndef ONLINE_JUDGE

//		debug();

	#endif

	dijkstra();

	printf("%d\n",dis[T]);

}

int main(){

	#ifndef ONLINE_JUDEG

//		freopen("hzlbn.in","r",stdin);

	#endif

	Init();

	Work();

	return 0;

}

巴特西

BZOJ2007/LG2046 「NOI2010」海拔平面图最小割转对偶图最短路

问题描述

题解

\(\mathrm{Code}\)

最新文章

热门文章

巴特西

BZOJ2007/LG2046 「NOI2010」海拔 平面图最小割转对偶图最短路

问题描述

题解

\(\mathrm{Code}\)

最新文章

热门文章

BZOJ2007/LG2046 「NOI2010」海拔平面图最小割转对偶图最短路