首页 > 代码库 > NOIP 2013 火车运输【Kruskal + 树链剖分】
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。
—————————————————————分割线—————————————————————
分析：
货车要运输尽可能多的货物，一定要保证两点间的路径上载重尽可能大，即，两点间的最大载重路径一定在最大生成树上，否则，与最大生成树的定义相悖。
只需要求解，在最大生成树上的两点间路径上的最大载重，这里使用树链剖分解决。
[ATTENTION]:这里注意点权和边权的处理，E_val[]表示该节点与其父节点连边的边权。根节点的E_val[]设置为 INF，可以视为加入一个虚拟节点(如图) ，再用线段树维护即可。
注释&代码：
Code By SHHHS
1 #include "bits/stdc++.h" 2 3 using namespace std ; 4 5 struct MST{int x , y , val ; } ; 6 struct Edge{int to , next , val ; } ; 7 struct SegTree{int l , r , mintr ; } ; 8 const int INF = 2147483647 ; 9 const int maxN = 300010 ; 10 typedef long long QAQ ; 11 12 MST MST_e[ maxN ] ; 13 Edge e [ maxN ] ; 14 SegTree tr[ maxN << 2 ] ; 15 int head[maxN] , father[maxN], DFN[maxN], hv[maxN],rank[maxN], E_val[maxN], start[maxN], pre[maxN]; 16 bool vis[maxN] ; 17 18 int cnt , dfs_num ; 19 QAQ Ans = INF ; 20 21 void Init ( int n ){for ( int i = 1 ; i <= n ; ++i )father[ i ] = i ; } 22 int getfa ( int x ){if(father[x] == x)return x ; else return father[ x ] = getfa( father[ x ] ) ; } 23 inline bool cmp ( MST x , MST y ){ return x.val > y.val ; } 24 inline int gmin ( int x , int y ){ return x > y ? y : x ; } 25 inline void Union_Set ( const int x , const int y ){ father[ x ] = y ; } 26 inline void Push_up ( int i ){tr[ i ].mintr = gmin (tr[ i << 1 | 1 ].mintr, tr[ i << 1 ].mintr) ; } 27 inline void gswap ( int &x , int &y ) {int temp = x ; x = y ; y = temp ; } 28 29 void Build_Tree ( int x , int y , int i ) {//建树 30 tr[ i ].l = x ; 31 tr[ i ].r = y ; 32 if ( x == y ) tr[ i ].mintr = E_val[ rank[ x ] ] ; 33 else { 34 int mid = ( tr[ i ].l + tr[ i ].r ) >> 1 ; 35 Build_Tree ( x , mid , i << 1 ) ; 36 Build_Tree ( mid + 1 , y , i << 1 | 1 ) ; 37 Push_up ( i ) ; 38 } 39 } 40 41 inline void Add_Edge ( const int x , const int y , const int _val ) {//建边 42 e[ ++cnt ].to = y ; 43 e[ cnt ].val = _val ; 44 e[ cnt ].next = head[ x ] ; 45 head[ x ] = cnt ; 46 } 47 48 void MST ( int N , int M ) {//最大生成树 49 int cnt_ = 0 ; 50 Init ( N ) ; 51 sort ( MST_e + 1 , MST_e + M + 1 , cmp ) ;//排序 52 for ( int i = 1 ; i <= M ; ++i ) { 53 int px = getfa ( MST_e[i].x ) ;//祖先 54 int py = getfa ( MST_e[i].y ) ;// 55 if ( px == py ) continue ; 56 else { 57 Union_Set ( px , py ) ; 58 Add_Edge ( MST_e[i].x , MST_e[i].y , MST_e[i].val ) ;//建边 59 Add_Edge ( MST_e[i].y , MST_e[i].x , MST_e[i].val ) ; 60 ++cnt_ ; 61 } 62 if ( cnt_ == N - 1 ) break ; 63 } 64 } 65 66 int Init_DFS ( const int x , const int fa ) { 67 vis[ x ] = true ; 68 int cnt_ = 1 , max_ = 0 ; 69 for ( int i = head[ x ] ; i ; i = e[ i ].next ) { 70 int temp = e[ i ].to ; 71 if ( temp == fa ) continue ; 72 int _ = Init_DFS ( temp , x ) ; 73 if ( _ > max_ ) { 74 max_ = _ ; 75 hv[ x ] = temp ; 76 } 77 cnt_ += _; 78 } 79 return cnt_ ; 80 } 81 82 void DFS ( const int x , const int fa ) { 83 vis [ x ] = false ; 84 if ( !start[ x ] ) start[ x ] = start[ fa ] ; 85 DFN[ x ] = ++ dfs_num ; 86 rank[ dfs_num ] = x ; 87 if ( hv[ x ] ) DFS ( hv[ x ] , x ) ; 88 for ( int i = head[ x ] ; i ; i = e[ i ].next ) { 89 if ( e[ i ].to == fa ) continue ; 90 E_val[ e[ i ].to ] = e[ i ] .val ; 91 if ( e[ i ].to != hv[ x ] && e[ i ].to != fa && vis[ e[ i ].to ] == true ) { 92 int temp = e[ i ].to ; 93 start[ temp ] = temp ; 94 pre [ temp ] = x ; 95 DFS ( temp , x ) ; 96 } 97 } 98 } 99 100 QAQ Query_Tree ( int q , int w , int i ) {//线段树查询 101 if ( q <= tr[i].l && w >= tr[i].r ) return tr[i].mintr;102 else {103 int mid = ( tr[ i ].l + tr[ i ].r ) >> 1 ;104 if ( q > mid ) return Query_Tree ( q , w , i << 1 | 1) ;105 else if ( w <= mid ) return Query_Tree ( q , w , i << 1 ) ;106 else return gmin ( Query_Tree ( q , w , i << 1 | 1 ) , Query_Tree ( q , w , i << 1 ) ) ;107 }108 }109 110 void Solve ( const int x , const int y ) {111 int px = x , py = y ;112 while ( start[ px ] != start[ py ] ) {//不在同一条链上 113 if ( DFN[ start[ px ] ] > DFN[ start[ py ] ] ) {//px跳 114 Ans = gmin ( Ans , Query_Tree ( DFN[start[ px ]] , DFN[px] , 1 ) ) ;115 px = pre[ start[ px ] ] ;116 }117 else {//py跳 118 Ans = gmin ( Ans , Query_Tree ( DFN[start[ py ]] , DFN[py] , 1 ) ) ;119 py = pre[ start[ py ] ] ;120 }121 }122 123 if ( px == py ) return ;124 int dfn_px = DFN[ px ] , dfn_py = DFN[ py ] ;125 if ( dfn_px > dfn_py ) gswap ( dfn_px , dfn_py ) ;//不加这句话会炸栈 126 Ans = gmin ( Ans , Query_Tree ( dfn_px + 1, dfn_py , 1 ) );127 }128 129 void DEBUG__ ( int n ){130 putchar ( ‘\n‘ ) ;131 for ( int i = 1 ; i <= n ; ++i )printf ("%d : %d %d\n", i , E_val[rank[ i ] ] , E_val[ i ]) ;132 putchar ( ‘\n‘ ) ;133 }134 void DEBUG_ ( int m ) {135 putchar(‘\n‘);136 for ( int i = 1 ; i <= m ; ++i ) printf ("%d %d %d\n" , MST_e[ i ].x , MST_e[ i ].y , MST_e[ i ].val) ;137 }138 int main ( ) {139 int N , M , Q , _x , _y ;140 scanf ( "%d%d" , &N , &M ) ;141 for ( int i = 1 ; i <= M ; ++i )//读入 142 scanf ( "%d%d%d" , &MST_e[ i ].x , &MST_e[ i ].y , &MST_e[ i ].val ) ;143 MST ( N , M ) ;//最大生成树 144 for ( int i = 1 ; i <= N ; ++i ) {//第一遍DFS 145 if ( !vis[i] ) {146 Init_DFS ( i , i ) ;147 start[ i ] = i ;148 E_val[ i ] = INF ;149 }150 }151 152 //DEBUG_( M );153 for ( int i = 1 ; i <= N ; ++i ) {//第二遍重儿子优先的DFS 154 if ( vis[ i ] ) {155 DFS ( i , i ) ;156 }157 }158 159 Build_Tree ( 1 , dfs_num , 1 ) ;//建树 160 161 //DEBUG__( dfs_num ) ;162 scanf ( "%d" , &Q ) ;163 while ( Q-- ){164 Ans = INF ;//设置最大值 165 scanf ( "%d%d" , &_x , &_y ) ;166 if ( getfa( _x ) == getfa( _y ) ) {//在一棵树上可相互到达 167 Solve ( _x , _y ) ;168 printf ( "%lld\n" , Ans ) ;169 }170 else printf("-1\n");171 }172 return 0 ;173 }
2016-10-02 19:52:23
(完)
NOIP 2013 火车运输【Kruskal + 树链剖分】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。