现在的位置: 首页 > 综合 > 正文

【UVa】11354 Bond 最小生成树，动态LCA，倍增思想

2017年10月15日 ⁄ 综合 ⁄ 共 6686字 ⁄ 字号 小 中 大 ⁄ 评论关闭

Bond

Once again, James Bond is on his way tosaving the world. Bond's latest mission requires him to travel between severalpairs of cities in a certain country.

 

The country has N cities(numbered by 1, 2, . . .,N),connected byM bidirectionalroads. Bond is going to steal a vehicle, and drive along the roads from citys
to cityt. The country'spolice will be patrolling the roads, looking for Bond, however, not all roadsget the same degree of attention from the police.

 

More formally, for each road MI6has estimated its dangerousness, the higher it is, the more likely Bond isgoing to be caught while driving on this road. Dangerousness of a path froms tot
is defined asthe maximum dangerousness of any road on this path.

 

Now, it's your job to help Bond succeedin saving the world by finding the least dangerous paths for his mission.

 

 

Input

There will be at most 5 cases in theinput file.

The first line of each case contains twointegers
N, M (2 ≤ N≤ 50000,1≤ M ≤ 100000)– number of cities and roads. The nextM lines describe the roads. Thei-thof these lines contains three integers:xi,yi,
di (1 ≤xi,yi ≤
N, 0 ≤di ≤ 109)- the numbers of the cities connected by theith road and itsdangerousness.

 

Description of the roads is followed bya line containing an integerQ (1 ≤Q ≤ 50000),followed by
Q lines, thei-thof which contains two integerssi andti (1 ≤
si,ti  ≤N,
si !=ti).

 

Consecutive input sets are separated bya blank line.

 

Output

For each case, output Q lines, thei-thof which contains the minimum dangerousness of a path between citiessi andti. Consecutiveoutput blocks
are separated by a blank line.

 

The input filewill be such that there will always be at least one valid path.

 

Sample Input

Output for Sample Input

4 5

1 2 10

1 3 20

1 4 100

2 4 30

3 4 10

2

1 4

4 1

 

2 1

1 2 100

1

1 2

20

20

 

100

 

ProblemSetter: Ivan Krasilnikov 


题型：最小生成树，动态LCA，倍增思想

题目大意：

有n座城市通过m条双向道路相连，每条道路都有一个危险系数。你的任务是回答若干个询问，每个询问包含一个起点s和一个终点t，要求找到一条从s到t的路，使得途经所有边的最大危险系数最小。

输入最多包含5组数据。(2 <= n <= 50000 , 1 <= m <= 100000 )。询问有Q个(1 <= Q <= 50000 )。起点编号1~n。

题目分析：

本题要求的是瓶颈路，而且需要快速作答，首先求所有点的瓶颈路肯定是不行的，数组存不下。

那么我们可以改变策略，考虑先预处理，将信息组织成易于查询的结构。

曾经学过倍增算法（其实只是自己YY然后实现过，在ACDream的某道题上用过），但是画风太差，现在又重新学了一个。

首先我们先求最小生成树，考虑到是稀疏图我们用Kruskal算法求解，然后通过一次DFS将无根树转化成有根树，同时求出每个结点u的深度deep[u]（规定根结点深度为0，根结点的子节点深度为1，依此类推），父节点fa[u]，以及它与父节点之间的路径的权值cost[u]。

接下来预处理出anc和maxcost数组，其中anc[i][j]表示结点i的第 2^j 级祖先编号（anc[i][0]就是父亲fa[i]，anc[i][j] = -1 表示该祖先不存在），maxcost[i][j]表示结点i与它的 2^j 级祖先之间路径上的最大权值。预处理代码如下：

void preProcess () {//预处理出anc和maxcost数组
		REPF ( i , 1 , n ) {
			anc[i][0] = fa[i] ;// i^0 级祖先就是父亲
			maxcost[i][0] = cost[i] ;//i与fa[i]之间的最大权值就是cost[i]
			LOGF ( j , 1 , n )
				anc[i][j] = -1 ;
		}
		LOGF ( j , 1 , n )
			REPF ( i , 1 , n )
				if ( ~anc[i][j - 1] ) {
					int a = anc[i][j - 1] ;
					anc[i][j] = anc[a][j - 1] ;
					maxcost[i][j] = max ( maxcost[i][j - 1] , maxcost[a][j - 1] ) ;
					//选择i~anc[i][j - 1]中的最大权值和anc[i][j - 1]~anc[anc[i][j - 1][j - 1]中的最大权值
					//也就是i ~ (i^(j-1)) 和 (i^(j-1)) ~ i^j 中选取最大权值(子段的最大权值已经求出)
				}
	}//preProcess

有了这写预处理我们就可以编写在线查询处理过程了。假定查询的两个节点为p和q，并且p比q深（不是就交换），则可以先把p提升到和q同样深的位置（假设树是倒着长的），提升过程中先求出deep[q] + 1 ~ deep[p]之间的最大权值。然后利用二进制展开的方法不断将p和q同时往上“提”（先保证二者深度始终相等），同时更新最大边权。代码如下：

int query ( int p , int q ) {//查询两点间的最小瓶颈路
		int tmp , log = 0 , ans = -OO ;
		if ( deep[p] < deep[q] )//令p的深度大于等于q，不满足就交换
			swap ( p , q ) ;
		LOGF ( i , 1 , deep[p] + 1 )//得到p的最大log段( 满足 ( 1 << log ) <= deep[p] , 1 << ( log + 1 ) > deep[p] )
			++ log ;
		REPV ( i , log , 0 )//将p的深度降低到与q相同，同时求出p到q深度之间的最大权值
			if ( deep[p] - ( 1 << i ) >= deep[q] ) {//第2^i级祖先的深度大于等于q
				ans = max ( ans , maxcost[p][i] ) ;
				p = anc[p][i] ;//跳到2^i级祖先的位置
			}
		if ( p == q )//q是p的祖先，则之前的处理直接让p下降到q的位置，p、q之间的最大权值已经求出
			return ans ;//LCA返回p( p 等于 q )
		REPV ( i , log , 0 )//比较的前提是p、q深度相同
			if ( ~anc[p][i] && anc[p][i] != anc[q][i] ) {
				//p和q深度相同，判断一个即可
				//同时祖先不能是同一个，保证所比较的都是唯一路径上的边，否则会跳出最近公共祖先，得到错误结果
				ans = max ( ans , maxcost[p][i] ) ;
				ans = max ( ans , maxcost[q][i] ) ;
				p = anc[p][i] ;//跳
				q = anc[q][i] ;//跳
			}
		ans = max ( ans , cost[p] ) ;
		ans = max ( ans , cost[q] ) ;
		return ans ;//LCA返回fa[p]( 它也等于fa[q] )
	}//query

上述代码同样可以求出p和q的最近公共祖先。这样就在预处理O(nlogn)，查询O(logn)的时间内解决了问题。

写了一天，不过有收获，感觉不错，还需巩固。

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;

#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REPV( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define LOGF( j , a , b ) for ( int j = a ; ( 1 << j ) < b ; ++ j )
#define EDGE( i , x ) for ( int i = adj[x] ; ~i ; i = edge[i].n )
#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define clear( a , x ) memset ( a , x , sizeof a )

const int LOGN = 20 ;
const int MAXN = 50005 ;
const int MAXE = 100005 ;
const int OO = 0x3f3f3f3f ;
struct Line {
	int x , y , val ;
	void input () {
		scanf ( "%d%d%d" , &x , &y , &val ) ;
	}
	bool operator < ( const Line &a ) const {
		return val < a.val ;
	}
} ;

struct Edge {
	int v , w , n ;
	Edge ( int V = 0 , int W = 0 , int N  = 0 ) :
		v(V) , w(W) , n(N) {}
} ;

struct findAndUnion {
	int p[MAXN] ;
	int rank[MAXN] ;
	
	void init () {
		REP ( i , MAXN )
			p[i] = i , rank[i] = 1 ;
	}
	
	int find ( int x ) {//非递归查找+路径压缩
		int tmp , o = x , ans ;
		while ( p[o] != o )
			o = p[o] ;
		ans = o ;
		o = x ;
		while ( p[o] != o ) {
			tmp = p[o] ;
			p[o] = ans ;
			o = tmp ;
		}
		return ans ;
	}//find
	
	int Union ( int x , int y ) {//合并（按秩合并）
		int f1 = find ( x ) ;
		int f2 = find ( y ) ;
		if ( f1 != f2 ) {
			if ( rank[f1] <= rank[f2] ) {//秩小的合并到秩大的点上
				p[f1] = f2 ;
				if ( rank[f1] == rank[f2] )
					++ rank[f2] ;
			}
			else
				p[f2] = f1 ;
			return 1 ;
		}
		return 0 ;
	}//union
} ;

struct MST {
	//并查集
	findAndUnion F ;
	int p[MAXN] ;//并查集父节点
	
	Line line[MAXE] ;//读入边集
	
	Edge edge[MAXE] ;//最小生成树边集
	int adj[MAXN] , cntE ;//表头及指针
	
	//倍增处理及查询（可用于LCA）
	int maxcost[MAXN][LOGN] ;//maxcost[i][j]，最小瓶颈路
	int anc[MAXN][LOGN] ;//anc[i][j]表示结点i的第2^j级祖先，2^0就是父亲
	int cost[MAXN] ;//cost[i]表示i与父亲fa[i]之间的边权
	int fa[MAXN] ;//父节点
	int deep[MAXN] ;//结点深度
	
	int n , m ;//结点数，边数
	
	void init () {
		F.init () ;
		cntE = 0 ;
		clear ( adj , -1 ) ;
		clear ( deep , 0 ) ;
	}//init
	
	void addedge ( int u , int v , int w ) {
		edge[cntE] = Edge ( v , w , adj[u] ) ;
		adj[u] = cntE ++ ;
		edge[cntE] = Edge ( u , w , adj[v] ) ;
		adj[v] = cntE ++ ;
	}//addedge
	
	int kruskal () {//求最小生成树
		sort ( line , line + m ) ;
		int cnt = 0 , ans = 0 ;
		REP ( i , m ) {
			int tmp = F.Union ( line[i].x , line[i].y ) ;
			if ( tmp ) {
				++ cnt ;
				ans += line[i].val ;
				addedge ( line[i].x , line[i].y , line[i].val ) ;//添加树边
				if ( cnt == n - 1 )//已经得到所有树边，退出
					break ;
			}
		}
		return ans ;
	}//kruskal
	
	void dfs ( int u , int p ) {//得到有根树
		EDGE ( i , u ) {
			int v = edge[i].v ;
			if ( v == p ) continue ;
			fa[v] = u ;//v的父亲是u
			deep[v] = deep[u] + 1 ;
			cost[v] = edge[i].w ;
			dfs ( v , u ) ;
		}
	}//dfs
	
	void preProcess () {//预处理出anc和maxcost数组
		REPF ( i , 1 , n ) {
			anc[i][0] = fa[i] ;// i^0 级祖先就是父亲
			maxcost[i][0] = cost[i] ;//i与fa[i]之间的最大权值就是cost[i]
			LOGF ( j , 1 , n )
				anc[i][j] = -1 ;
		}
		LOGF ( j , 1 , n )
			REPF ( i , 1 , n )
				if ( ~anc[i][j - 1] ) {
					int a = anc[i][j - 1] ;
					anc[i][j] = anc[a][j - 1] ;
					maxcost[i][j] = max ( maxcost[i][j - 1] , maxcost[a][j - 1] ) ;
					//选择i~anc[i][j - 1]中的最大权值和anc[i][j - 1]~anc[anc[i][j - 1][j - 1]中的最大权值
					//也就是i ~ (i^(j-1)) 和 (i^(j-1)) ~ i^j 中选取最大权值(子段的最大权值已经求出)
				}
	}//preProcess
	
	int query ( int p , int q ) {//查询两点间的最小瓶颈路
		int tmp , log = 0 , ans = -OO ;
		if ( deep[p] < deep[q] )//令p的深度大于等于q，不满足就交换
			swap ( p , q ) ;
		LOGF ( i , 1 , deep[p] + 1 )//得到p的最大log段( 满足 ( 1 << log ) <= deep[p] , 1 << ( log + 1 ) > deep[p] )
			++ log ;
		REPV ( i , log , 0 )//将p的深度降低到与q相同，同时求出p到q深度之间的最大权值
			if ( deep[p] - ( 1 << i ) >= deep[q] ) {//第2^i级祖先的深度大于等于q
				ans = max ( ans , maxcost[p][i] ) ;
				p = anc[p][i] ;//跳到2^i级祖先的位置
			}
		if ( p == q )//q是p的祖先，则之前的处理直接让p下降到q的位置，p、q之间的最大权值已经求出
			return ans ;//LCA返回p( p 等于 q )
		REPV ( i , log , 0 )//比较的前提是p、q深度相同
			if ( ~anc[p][i] && anc[p][i] != anc[q][i] ) {
				//p和q深度相同，判断一个即可
				//同时祖先不能是同一个，保证所比较的都是唯一路径上的边，否则会跳出最近公共祖先，得到错误结果
				ans = max ( ans , maxcost[p][i] ) ;
				ans = max ( ans , maxcost[q][i] ) ;
				p = anc[p][i] ;//跳
				q = anc[q][i] ;//跳
			}
		ans = max ( ans , cost[p] ) ;
		ans = max ( ans , cost[q] ) ;
		return ans ;//LCA返回fa[p]( 它也等于fa[q] )
	}//query
} ;

MST tree ;

void work () {
	int q , u , v , flag = 0 ;
	while ( ~scanf ( "%d%d" , &tree.n , &tree.m ) ) {
		if ( flag )
			puts ( "" ) ;
		flag = 1 ;
		tree.init () ;
		REP ( i , tree.m )
			tree.line[i].input () ;
		tree.kruskal () ;//求最小生成树
		tree.dfs ( 1 , 0 ) ;//无根树转有根树
		tree.preProcess () ;//倍增查询预处理
		scanf ( "%d" , &q ) ;
		while ( q -- ) {
			scanf ( "%d%d" , &u , &v ) ;
			printf ( "%d\n" , tree.query ( u , v ) ) ;
		}
	}
}

int main () {
	work () ;
	return 0 ;
}

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞