NOIP 2013 货车运输【Kruskal + 树链剖分 + 线段树】【倍增】

NOIP 2013 货车运输【树链剖分】

题目描述 Description

A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

输入描述 Input Description

第一行有两个用一个空格隔开的整数 n，m，表示 A 国有 n 座城市和 m 条道路。
接下来 m 行每行 3 个整数 x、y、z，每两个整数之间用一个空格隔开，表示从 x 号城市到 y 号城市有一条限重为 z 的道路。注意：x 不等于 y，两座城市之间可能有多条道路。
接下来一行有一个整数 q，表示有 q 辆货车需要运货。
接下来 q 行，每行两个整数 x、y，之间用一个空格隔开，表示一辆货车需要从 x 城市运输货物到 y 城市，注意：x 不等于 y。

输出描述 Output Description

输出共有 q 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货车不能到达目的地，输出-1。

样例输入 Sample Input

4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3

样例输出 Sample Output

3
-1
3

数据范围及提示 Data Size & Hint

对于 30%的数据，0 < n < 1,000，0 < m < 10,000，0 < q < 1,000；
对于 60%的数据，0 < n < 1,000，0 < m < 50,000，0 < q < 1,000；
对于 100%的数据，0 < n < 10,000，0 < m < 50,000，0 < q < 30,000，0 ≤ z ≤ 100,000。

—————————————————————分割线—————————————————————

分析：

货车要运输尽可能多的货物，一定要保证两点间的路径上载重尽可能大，即，两点间的最大载重路径一定在最大生成树上，否则，与最大生成树的定义相悖。

只需要求解，在最大生成树上的两点间路径上的最大载重，这里使用树链剖分解决。

Gster大爷说这道题可以用树剖写，于是就尝试了树剖。

[ATTENTION]:这里注意点权和边权的处理，E_val[]表示该节点与其父节点连边的边权。根节点的E_val[]设置为 INF，可以视为加入一个虚拟节点(如图) ，再用线段树维护即可。

注释&代码：

Code By SHHHS

解法一：

  1 /* 
  2     树链剖分
  3     author : SHHHS
  4     2016-10-02 09:04:15 
  5 */ 
  6 #include "bits/stdc++.h"
  7 
  8 using namespace std ;
  9 
 10 struct MST{int x , y , val ; } ;
 11 struct Edge{int to , next , val ; } ;
 12 struct SegTree{int l , r , mintr ; } ;
 13 const int INF = 2147483647 ;
 14 const int maxN = 300010 ;
 15 typedef long long QAQ ;
 16 
 17 MST MST_e[ maxN ] ;
 18 Edge e [ maxN ] ;
 19 SegTree tr[ maxN << 2 ] ;
 20 int head[maxN] , father[maxN], DFN[maxN], hv[maxN],rank[maxN], E_val[maxN], start[maxN], pre[maxN];
 21 bool vis[maxN] ;
 22 
 23 int cnt , dfs_num ;
 24 QAQ Ans = INF ;
 25 
 26 void Init ( int n ){for ( int i = 1 ; i <= n ; ++i )father[ i ] = i ; }
 27 int getfa ( int x ){if(father[x] == x)return x ; else return father[ x ] = getfa( father[ x ] ) ; }
 28 inline bool cmp ( MST x , MST y ){ return x.val > y.val ; }
 29 inline int gmin ( int x , int y ){ return x > y ? y : x ; }
 30 inline void Union_Set ( const int x , const int y ){ father[ x ] = y ; }
 31 inline void Push_up ( int i ){tr[ i ].mintr = gmin (tr[ i << 1 | 1 ].mintr, tr[ i << 1 ].mintr) ; }
 32 inline void gswap ( int &x , int &y ) {int temp = x ; x = y ; y = temp ; }
 33 bool Check ( const int x , const int y ) { return getfa( x ) == getfa( y ) ? true : false ; }
 34 
 35 void Build_Tree ( int x , int y , int i ) {//建树 
 36         tr[ i ].l = x ;
 37         tr[ i ].r = y ;
 38         if ( x == y ) tr[ i ].mintr = E_val[ rank[ x ] ] ;
 39         else {
 40                 int mid = ( tr[ i ].l + tr[ i ].r ) >> 1 ;
 41                 Build_Tree ( x , mid , i << 1 ) ;
 42                 Build_Tree ( mid + 1 , y , i << 1 | 1 ) ;
 43                 Push_up ( i ) ;
 44         }
 45 }
 46 
 47 inline void Add_Edge ( const int x , const int y , const int _val ) {//建边 
 48         e[ ++cnt ].to = y ;
 49         e[ cnt ].val = _val ;
 50         e[ cnt ].next = head[ x ] ;
 51         head[ x ] = cnt ;
 52 }
 53 
 54 void MST ( int N , int M ) {//最大生成树 
 55         int cnt_ = 0 ;
 56         Init ( N ) ;
 57         sort ( MST_e + 1 , MST_e + M + 1 , cmp ) ;//排序 
 58         for ( int i = 1 ; i <= M ; ++i ) {
 59                 int px = getfa ( MST_e[i].x ) ;//祖先 
 60                 int py = getfa ( MST_e[i].y ) ;// 
 61                 if ( px == py ) continue ;
 62                 else {
 63                         Union_Set ( px , py ) ;
 64                         Add_Edge ( MST_e[i].x , MST_e[i].y , MST_e[i].val ) ;//建边 
 65                         Add_Edge ( MST_e[i].y , MST_e[i].x , MST_e[i].val ) ;
 66                         ++cnt_ ;
 67                 }
 68                 if ( cnt_ == N - 1 ) break ;
 69         }
 70 }
 71 
 72 int Init_DFS ( const int x , const int fa ) {
 73         vis[ x ] = true ;
 74         int cnt_ = 1 , max_ = 0 ;//cnt_儿子数 
 75         for ( int i = head[ x ] ; i ; i = e[ i ].next ) {
 76                 int temp = e[ i ].to ;//下一个节点 
 77                 if ( temp == fa ) continue ;
 78                 int _ = Init_DFS ( temp , x ) ;//启发式建链 
 79                 if ( _ > max_ ) {
 80                         max_ = _ ;
 81                         hv[ x ] = temp ;
 82                 }
 83                 cnt_ += _;
 84         }   
 85         return cnt_ ;
 86 }
 87 
 88 void DFS ( const int x , const int fa ) {
 89         vis [ x ] = false ;
 90         if ( !start[ x ] ) start[ x ] = start[ fa ] ;//链头 
 91         DFN[ x ] = ++ dfs_num ;// DFS序 
 92         rank[ dfs_num ] = x ;// 节点在DFN数组中的位置 
 93         if ( hv[ x ] ) DFS ( hv[ x ] , x ) ;//重儿子优先DFS 
 94         for ( int i = head[ x ] ; i ; i = e[ i ].next ) {
 95                 if ( e[ i ].to == fa ) continue ;
 96                 E_val[ e[ i ].to ] = e[ i ] .val ;
 97                 if ( e[ i ].to != hv[ x ] && e[ i ].to != fa && vis[ e[ i ].to ] == true ) {
 98                         int temp = e[ i ].to ;
 99                         start[ temp ] = temp ;
100                         pre [ temp ] = x ;
101                         DFS ( temp , x ) ;
102                 }
103         }
104 }
105 
106 QAQ Query_Tree ( int q , int w , int i ) {//线段树查询 
107         if ( q <= tr[i].l && w >= tr[i].r ) return tr[i].mintr;
108         else {
109                 int mid = ( tr[ i ].l + tr[ i ].r ) >> 1 ;
110                 if ( q > mid ) return Query_Tree ( q , w , i << 1 | 1) ;
111                 else if ( w <= mid ) return Query_Tree ( q , w , i << 1 ) ;
112                 else return gmin ( Query_Tree ( q , w , i << 1 | 1 ) , Query_Tree ( q , w , i << 1 ) ) ;
113         }
114 }
115 
116 void Solve ( const int x , const int y ) {
117         int px = x , py = y ;
118         while ( start[ px ] != start[ py ] ) {//不在同一条链上 
119                 if ( DFN[ start[ px ] ] > DFN[ start[ py ] ] ) {//px跳 
120                         Ans = gmin ( Ans , Query_Tree ( DFN[start[ px ]] , DFN[px] , 1 ) ) ;
121                         px = pre[ start[ px ] ] ;
122                 }
123                 else {//py跳 
124                         Ans = gmin ( Ans , Query_Tree ( DFN[start[ py ]] , DFN[py] , 1 ) ) ;
125                         py = pre[ start[ py ] ] ;
126                 }
127         }
128 
129         if ( px == py ) return ;
130         int dfn_px = DFN[ px ] , dfn_py = DFN[ py ] ;
131         if ( dfn_px  > dfn_py ) gswap ( dfn_px , dfn_py ) ;//不加这句话会炸栈 
132         Ans = gmin ( Ans , Query_Tree ( dfn_px + 1, dfn_py , 1 ) );
133 }
134 
135 void DEBUG__ ( int n ){
136         putchar ( '
' ) ;
137         for ( int i = 1 ; i <= n ; ++i )printf ("%d : %d %d
", i , E_val[rank[ i ] ] , E_val[ i ]) ;
138         putchar ( '
' ) ;
139 }
140 void DEBUG_ ( int m ) {
141         putchar('
');
142         for ( int i = 1 ; i <= m ; ++i ) printf ("%d %d %d
" , MST_e[ i ].x , MST_e[ i ].y , MST_e[ i ].val) ;
143 }
144 int main ( ) {
145         int N , M , Q , _x , _y ;
146         scanf ( "%d%d" , &N , &M ) ;
147         for ( int i = 1 ; i <= M ; ++i )//读入 
148                 scanf ( "%d%d%d" , &MST_e[ i ].x , &MST_e[ i ].y , &MST_e[ i ].val ) ;
149         MST ( N , M ) ;//最大生成树 
150         for ( int i = 1 ; i <= N ; ++i ) {//第一遍DFS 
151                 if ( !vis[i] ) {
152                         Init_DFS ( i , i ) ;
153                         start[ i ] = i ;
154                         E_val[ i ] = INF ;
155                 }
156         }
157         
158         //DEBUG_( M );
159         for ( int i = 1 ; i <= N ; ++i ) {//第二遍重儿子优先的DFS 
160                 if ( vis[ i ] ) {
161                         DFS ( i , i ) ;
162                 }
163         }
164         
165         Build_Tree ( 1 , dfs_num , 1 ) ;//建树 
166 
167         //DEBUG__( dfs_num ) ;
168         scanf ( "%d" , &Q ) ;
169         while ( Q-- ){
170                 Ans = INF ;//设置最大值 
171                 scanf ( "%d%d" , &_x , &_y ) ;
172                 if ( Check ( _x , _y ) ) {//在一棵树上可相互到达 
173                         Solve ( _x , _y ) ;
174                         printf ( "%lld
" , Ans ) ;
175                 }
176                 else printf("-1
");
177         }
178         return 0 ;
179 }

解法二：

倍(béi)增算法

  1 /*
  2     树上倍增
  3     Code By SHHHS
  4     2016-10-04 12:20:10 
  5 */
  6 #include "bits/stdc++.h"
  7 
  8 using namespace std;
  9 struct MST { int x,y,val;};
 10 struct Edge{int to,next,val;};
 11 const int INF = 2147483647 ;
 12 const int maxN = 100100 ;
 13 
 14 MST MST_e[ maxN ] ;
 15 Edge e[ maxN ] ;
 16 int father[maxN],deep[maxN],fa[maxN][21],g[maxN][21],head[maxN],cnt;
 17 bool vis[maxN];
 18 
 19 inline bool cmp ( MST x , MST y ) {  return x.val > y.val ; }
 20 inline void Init ( int n ) { for ( int i=1 ; i<=n ; ++i ) father[ i ] = i ;}
 21 int getfa( int x ){ return father[ x ] == x ? x : father[ x ] = getfa( father[ x ] ) ; }
 22 inline void Union_Set ( const int x , const int y ){ father[ x ] = y ; }
 23 inline int gmin ( int x , int y ) { return x > y ? y : x ;}
 24 inline void gswap ( int &x , int &y ) { int temp = x ; x = y ; y = temp ; }
 25 
 26 void DFS ( int x , int pre ) {
 27         vis[ x ] = true ;
 28         for ( int i=1 ; i<=20 ; ++i ) {
 29                 if ( deep[ x ] < ( 1 << i ) ) break ;
 30                 fa[ x ][ i ] = fa[ fa[ x ][ i - 1 ] ][ i - 1 ] ;
 31                 g[ x ][ i ] = gmin ( g[ x ][ i - 1 ] , g[ fa[ x ][ i - 1 ] ][ i - 1 ] ) ;
 32         }
 33         for ( int i=head[ x ] ; i ; i=e[ i ].next ){
 34                 int temp = e[ i ].to ;
 35                 if( vis[ temp ] ||temp == pre ) continue;
 36                 fa[ temp ][ 0 ] = x ;g[ temp ][ 0 ] = e[ i ].val ;
 37                 deep[ temp ] = deep[ x ] + 1 ;
 38                 DFS ( temp , x ) ;
 39         }
 40 }
 41 
 42 void Add_Edge ( const int x , const int y , const int _val ) {
 43         e[ ++cnt ].to = y ;
 44         e[ cnt ].val = _val ; 
 45         e[ cnt ].next = head[ x ] ;
 46         head[ x ] = cnt ;
 47 } 
 48 
 49 int LCA ( int x , int y ) {
 50         if ( deep[ x ] < deep[ y ] )gswap( x , y ) ;
 51         int t = deep[ x ] - deep[ y ] ;
 52         for ( int i=0 ; i<=20 ; ++i ) if( ( 1 << i ) & t ) x = fa[ x ][ i ] ;
 53         if( x == y ) return x ;
 54         for ( int i=20 ; i>=0 ; --i ) {
 55                 if ( fa[ x ][ i ] == fa[ y ][ i ] ) continue ;
 56                 x = fa[ x ][ i ] ; y = fa[ y ][ i ] ;
 57         }
 58         return fa[ x ][ 0 ] ;
 59 }
 60 
 61 int solve ( int x , int y ) {
 62         int ans = INF ;
 63         if ( deep[ x ] < deep[ y ] )gswap( x , y ) ;
 64         int t = deep[ x ] - deep[ y ] ;
 65         for ( int i=0 ; i<=20 ; ++i ) if( ( 1 << i ) & t )ans = gmin( ans , g[ x ][ i ] ) ,x = fa[ x ][ i ] ;
 66         if ( x == y ) return ans ;
 67         for ( int i=20 ; i>=0 ; --i ) {
 68                 if ( fa[ x ][ i ] == fa[ y ][ i ] ) continue ;
 69                 ans = gmin ( ans , gmin ( g[ x ][ i ] , g[ y ][ i ] ) ) ;
 70                 x = fa[ x ][ i ];
 71                 y = fa[ y ][ i ] ;
 72         }
 73         return gmin ( ans ,gmin ( g[ x ][ 0 ] ,g[ y ][ 0 ] ) ) ;
 74 }
 75 
 76 void Kruskal ( int N , int M ) { 
 77         int cnt_ = 0 ;
 78         Init ( N ) ;
 79         sort ( MST_e + 1 , MST_e + M + 1 , cmp ) ;
 80         for ( int i = 1 ; i <= M ; ++i ) {
 81                 int px = getfa ( MST_e[i].x ) ;
 82                 int py = getfa ( MST_e[i].y ) ; 
 83                 if ( px == py ) continue ;
 84                 else {
 85                         Union_Set ( px , py ) ;
 86                         Add_Edge ( MST_e[i].x , MST_e[i].y , MST_e[i].val ) ;
 87                         Add_Edge ( MST_e[i].y  , MST_e[i].x , MST_e[i].val ) ;
 88                         ++cnt_ ;
 89                 }
 90                 if ( cnt_ == N - 1 ) break ;
 91         }
 92 }
 93 
 94 int main ( ) {
 95         memset ( g , 127/3 , sizeof( g ) ) ;
 96         int N , M , x , y , Q ;
 97         scanf ( "%d%d" , &N , &M ) ;
 98         for ( int i=1 ; i<=M ; i++ )
 99                 scanf( "%d%d%d" , &MST_e[ i ].x , &MST_e[ i ].y , &MST_e[ i ].val ) ;
100         Kruskal ( N , M ) ;
101         for ( int i=1 ; i<=N ; ++i )
102                 if( !vis[ i ] ) 
103                         DFS ( i , i ) ;
104         scanf ( "%d" , &Q ) ;
105         while ( Q-- ) {
106                 scanf( "%d%d" , &x , &y ) ;
107                 if ( getfa( x ) != getfa( y ) )printf( "-1
" ) ;
108                 else  {
109                         int lca = LCA ( x , y ) ;
110                         printf ( "%d
" , gmin ( solve( lca , x ) , solve ( lca , y ) ) ) ;
111                 }
112         }
113         return 0;
114 }

2016-10-02 19:52:23

(完)

NOIP 2013 货车运输【Kruskal + 树链剖分 + 线段树 】【倍增】

NOIP 2013 货车运输【Kruskal + 树链剖分 + 线段树】【倍增】