海拔

luoguP2046 [NOI2010] 海拔

题目描述

YT 市是一个规划良好的城市，城市被东西向和南北向的主干道划分为 \(n \times n\) 个区域。简单起见，可以将 YT 市看作 一个正方形，每一个区域也可看作一个正方形。从而，YT 城市中包括 \((n+1) \times (n+1)\) 个交叉路口和 \(2n \times (n+1)\) 条双向道路（简称道路），每条双向道路连接主干道上两个相邻的交叉路口。下图为一张 YT 市的地图（\(n = 2\)），城市被划分为 \(2 \times 2\) 个区域，包括 \(3 \times 3\) 个交叉路口和 \(12\) 条双向道路。

小 Z 作为该市的市长，他根据统计信息得到了每天上班高峰期间 YT 市每条道路两个方向的人流量，即在高峰期间沿着该方向通过这条道路的人数 \(w_i\)。每一个交叉路口都有不同的海拔高度值，YT 市市民认为爬坡是一件非常累的事情，每向上爬 \(h\) 的高度，就需要消耗 \(h\) 的体力。如果是下坡的话，则不需要耗费体力。因此如果一段道路的终点海拔减去起点海拔的值为 \(h\)（注意 \(h\) 可能是负数），那么一个人经过这段路所消耗的体力是 \(\max\{0,h\}\)。

小 Z 还测量得到这个城市西北角的交叉路口海拔为 \(0\)，东南角的交叉路口海拔为 \(1\)（如上图所示），但其它交叉路口的海拔高度都无法得知。小 Z 想知道在最理想的情况下（即你可以任意假设其他路口的海拔高度），每天上班高峰期间所有人爬坡消耗的总体力和的最小值。

数据范围：\(1\le n\le 500,0\le w_i \le 10^6\)，且所有流量均为整数。

解法：

由题，要求总体力和的最小值，一件非常显然的事情就是，所有城市的海拔只会是 \(0\) 或 \(1\)，因为如果是其他的值，那爬下去不消耗体力，但是爬上来要消耗更多的体力，所以肯定不是最优的。

然后我们考虑每一条路径，如果说只有 \(0\) 和 \(1\) 的话，那么显然是让他在每条路径上只变化一次，即 \(0\) 和 \(1\) 的分界线只有一个，那么对于整个图上所有的路径只有一个分界线，那么就意味着在这样图上有一条 \(01\) 的分界线将图分成了两部分，一部分连接起点，一部分连接终点。

想到这里，正解就出来一半了，这显然就是求最小割的板子。但是直接求最小割是不行的，因为 \(n\) 的范围在 \(500\)， \(n^2\) 的范围就是 \(250000\)，如果直接跑最小割显然会爆掉。

对于这种情况，我们引入一个叫对偶图的东西。

我们正常求最小割，都是对着平面图跑的，而且都用到了定理“最大流等于最小割”，这些所有的算法复杂度都是三次方级别左右的，在数据范围小的时候可以，但是数据范围一大就不好使了，这时候一种对最小割求法的优化，对偶图就应运而生。

对平面图求最小割的时候，其实就是求一条能够将原图割成两半的一条路径（即原题目的），我们可以将平面上每个节点围成的一个面当做一个节点，每两个相邻的面肯定会有一条边将其分开，那这两个面所对应的节点就会相应的有一条边，这条边的权值就是这条将这两个面分开的边的容量。

在最外层，如果要求能将图割成两半的路径的话，那么显然要将原图最外层的部分分成两部分，被起点和终点隔开。如下图：

在这个图中黑色的点表示原图的点，红色的表示原图建成的对偶图所对应的点。黑色的线条表示原图中的路径，蓝色的表示对偶图中的边，灰色的表示辅助边。

所以我们对上图中 \(S-T\) 的最小值就是红色节点 \(1-6\) 的最短路。对于此题的话，用Dijkstra就行。

Code：

#include 
#include 
#include 
using namespace std ;

const int N = 2500005 ;
int n , s , t , dis[N] ;

struct Edge
{
	int nxt , to , len ;
} edge[N*10] ;

int cnt = 1 , head[N] , cur[N] ;
void insert ( int u , int v , int w )
{
	edge [ ++ cnt ] .nxt = head [ u ] ;
	edge [ cnt ] .to = v ;
	edge [ cnt ] .len = w ;
	head [ u ] = cnt ;
}

struct Dist
{
	int x , dist ;
	Dist ( int _x = 0 , int _dist = -1 ) : x ( _x ) , dist ( _dist ) { }
	bool operator ( ) ( Dist u , Dist v )
	{
		return u .dist > v .dist ;
	}
} ;

priority_queue < Dist , vector < Dist > , Dist > q ;

void Dijkstra ( )
{
	memset ( dis , 0x3f , sizeof ( dis ) ) ;
	dis [ s ] = 0 ;
	q .push ( Dist ( s , 0 ) ) ;
	while ( ! q .empty ( ) )
	{
		Dist tmp = q .top ( ) ; q .pop ( ) ;
		int x = tmp .x ;
		if ( dis [ x ] != tmp .dist )
			continue ;
		for ( int i = head [ x ] ; i ; i = edge [ i ] .nxt )
		{
			int y = edge [ i ] .to ;
			if ( dis [ y ] > dis [ x ] + edge [ i ] .len )
			{
				dis [ y ] = dis [ x ] + edge [ i ] .len ;
				q .push ( Dist ( y , dis [ y ] ) ) ;
			}
		}
	}
}

int id ( int x , int y )
{
	return ( x - 1 ) * ( n + 1 ) + y ;
}

signed main ( )
{
	cin >> n ;
	t = ( n + 1 ) * ( n + 1 ) + 1 ;
	int x ;
	for ( int i = 1 ; i <= n + 1 ; ++ i )
		for ( int j = 1 ; j <= n ; ++ j )
		{
			cin >> x ;
			if ( i == 1 )
				insert ( s , id ( i , j ) , x ) ;
			else if ( i == n + 1 )
				insert ( id ( i - 1 , j ) , t , x ) ;
			else
				insert ( id ( i - 1 , j ) , id ( i , j ) , x ) ;
		}
	for ( int i = 1 ; i <= n ; ++ i )
		for ( int j = 1 ; j <= n + 1 ; ++ j )
		{
			cin >> x ;
			if ( j == 1 )
				insert ( id ( i , j ) , t , x ) ;
			else if ( j == n + 1 )
				insert ( s , id ( i , j - 1 ) , x ) ;
			else
				insert ( id ( i , j ) , id ( i , j - 1 ) , x ) ;
		}
	for ( int i = 1 ; i <= n + 1 ; ++ i )
		for ( int j = 1 ; j <= n ; ++ j )
		{
			cin >> x ;
			if ( i == 1 )
				insert ( id ( i , j ) , s , x ) ;
			else if ( i == n + 1 )
				insert ( t , id ( i - 1 , j ) , x ) ;
			else
				insert ( id ( i , j ) , id ( i - 1 , j ) , x ) ;
		}
	for ( int i = 1 ; i <= n ; ++ i )
		for ( int j = 1 ; j <= n + 1 ; ++ j )
		{
			cin >> x ;
			if ( j == 1 )
				insert ( t , id ( i , j ) , x ) ;
			else if ( j == n + 1 )
				insert ( id ( i , j - 1 ) , s , x ) ;
			else
				insert ( id ( i , j - 1 ) , id ( i , j ) , x ) ;
		}
	Dijkstra ( ) ;
	cout << dis [ t ] << '\n' ;
	return 0 ;
}