[NOI2018] 歸程

• description
• solution1
• code1
• solution2
• code

description

題目描述

本題的故事發生在魔力之都，在這里我們將為你介紹一些必要的設定

魔力之都可以抽象成一個$n$個節點、$m$條邊的無向連通圖（節點的編號從$1$至$n$）我們依次用 $l,a$描述一條邊的長度、海拔

作為季風氣候的代表城市，魔力之都時常有雨水相伴，因此道路積水總是不可避免的。由于整個城市的排水系統連通，因此有積水的邊一定是海拔相對最低的一些邊

我們用水位線來描述降雨的程度，它的意義是：所有海拔不超過水位線的邊都是有積水的

Yazid 是一名來自魔力之都的 OIer，剛參加完 ION2018 的他將踏上歸程，回到他溫暖的家

Yazid 的家恰好在魔力之都的$1$號節點。對于接下來 Q 天，每一天 Yazid 都會告訴你他的出發點 v，以及當天的水位線 p

每一天，Yazid 在出發點都擁有一輛車。這輛車由于一些故障不能經過有積水的邊

Yazid 可以在任意節點下車，這樣接下來他就可以步行經過有積水的邊。但車會被留在他下車的節點并不會再被使用。

• 需要特殊說明的是，第二天車會被重置，這意味著：
  • 車會在新的出發點被準備好。
  • Yazid 不能利用之前在某處停放的車。

Yazid 非常討厭在雨天步行，因此他希望在完成回家這一目標的同時，最小化他步行經過的邊的總長度。請你幫助 Yazid 進行計算

本題的部分測試點將強制在線，具體細節請見「輸入格式」和「子任務」。

輸入格式

從文件 return.in 讀入數據

單個測試點中包含多組數據。輸入的第一行為一個非負整數 T，表示數據的組數。

接下來依次描述每組數據，對于每組數據：

第一行2個非負整數 n,m，分別表示節點數、邊數。

接下來 m行，每行4個正整數 u,v,l,a，描述一條連接節點 u,v 的、長度為 l、海拔為 a 的邊。在這里，我們保證 1≤u,v≤n

接下來一行3個非負數 Q,K,S，其中：Q表示總天數，K∈0,1是一個會在下面被用到的系數，S 表示的是可能的最高水位線。

接下來 Q 行依次描述每天的狀況。每行2個整數 v0,p0 描述一天：

• 這一天的出發節點為 v=(v0+K×lastans?1)modn+1

• 這一天的水位線為 p=(p0+K×lastans)mod(S+1)

其中 lastans 表示上一天的答案（最小步行總路程）

特別地，我們規定第 1 天 lastans=0

在這里，我們保證 1≤v0≤n,0≤p0≤S

對于輸入中的每一行，如果該行包含多個數，則用單個空格將它們隔開。

輸出格式

輸出到文件 return.out 中。

依次輸出各組數據的答案。對于每組數據：

輸出 Q 行每行一個整數，依次表示每天的最小步行總路程

樣例

樣例 1

1 4 3 1 2 50 1 2 3 100 2 3 4 50 1 5 0 2 3 0 2 1 4 1 3 1 3 2 0 50 200 50 150

第一天沒有降水，Yazid 可以坐車直接回到家中。

第二天、第三天、第四天的積水情況相同，均為連接 1,2 號節點的邊、連接 3,4 號點的邊有積水。

對于第二天，Yazid 從 2 號點出發坐車只能去往 3 號節點，對回家沒有幫助。因此 Yazid 只能純靠徒步回家。

對于第三天，從 4 號節點出發的唯一一條邊是有積水的，車也就變得無用了。Yazid 只能純靠徒步回家。

對于第四天，Yazid 可以坐車先到達 2 號節點，再步行回家。

第五天所有的邊都積水了，因此 Yazid 只能純靠徒步回家。

樣例 2

1 5 5 1 2 1 2 2 3 1 2 4 3 1 2 5 3 1 2 1 5 2 1 4 1 3 5 1 5 2 2 0 4 0 0 2 3 1

本組數據強制在線。

第一天的答案是 0，因此第二天的 v=(5+0?1)mod5+1=5,p=(2+0)mod(3+1)=2

第二天的答案是 2，因此第三天的 v=(2+2?1)mod5+1=4,p=(0+2)mod(3+1)=2

第三天的答案是 3，因此第四天的 v=(4+3?1)mod5+1=2,p=(0+3)mod(3+1)=3

數據范圍與提示

所有測試點均保證 T≤3，所有測試點中的所有數據均滿足如下限制：

n≤2×105，m≤4×105，Q≤4×105，K∈0,1，1≤S≤109

對于所有邊：l≤104，a≤109

任意兩點之間都直接或間接通過邊相連。

solution1

• 考慮沒有一條邊被淹。那就是$0$

• 考慮邊都被淹了。那就是問從起點到$1$的最短路

• 考慮淹了一些邊。沒有淹的邊可以隨便走，相當于是個連通塊

  所以就是求從起點所在連通塊到$1$所在連通塊的最短路

顯然，邊的存在跟每次給定的水位線有關，似乎只能在線維護了。

實則不然，如果我們將所有水位線的答案都提前處理出來，那么在線也就是離線了

這就是我們的——可持久化

最短路可以最開始跑一遍dijkstra解決

連通塊就是并查集問題，再加上$i$所在塊到$1$的最短路，就用線段樹維護

具體而言：將所有邊的水位從低到高排序，從后往前加入每一條邊

對于第$i$號版本的線段樹，維護的是所有海拔大于等于該邊構成的連通塊，以及在此時生成的圖上，每個點到$1$的最短路

初始時，每個點自己為一個連通塊t[now].fa=l,t[now].ans=dis[l]

一旦合并兩個連通塊（按秩合并）就在線段樹上新建版本，并修改t[now].fa=New_fa

如果新兒子最短路優于父親最短路，就又新建版本修改t[now].ans=ans

感覺有可能新建了兩個版本？？NO！

并查集修改是更改兒子v對應的父親，新建的$\log$個點是v一路上的

而答案更新是要更新父親u對應的答案，就又要新建$\log$個u一路上的點

屬于同一個版本root[i]

相當于在上一條邊對應的版本線段樹基礎上一共修改$2\log$個點，成為新的版本

最后就是詢問，直接找比所給水位線嚴格大于的所有高度都存在的版本

就是用upper_bound()找一下而已啦

code1

#include <queue> #include <cstdio> #include <vector> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define maxn 400005 #define int long long #define Pair pair < int, int > priority_queue < Pair, vector < Pair >, greater < Pair > > q; struct node { int l, r, fa, ans, h; }t[maxn * 20]; struct edge { int u, v, len, h; }E[maxn]; vector < edge > G[maxn]; int n, m, Q, K, S, cnt; int dis[maxn], root[maxn], high[maxn]; bool vis[maxn];void dijkstra() {memset( vis, 0, sizeof( vis ) );memset( dis, 0x7f, sizeof( dis ) );q.push( make_pair( dis[1] = 0, 1 ) );while( ! q.empty() ) {int u = q.top().second; q.pop();if( vis[u] ) continue;vis[u] = 1;for( int i = 0;i < G[u].size();i ++ ) {int v = G[u][i].v, len = G[u][i].len;if( dis[u] + len < dis[v] ) {dis[v] = dis[u] + len;q.push( make_pair( dis[v], v ) );}}} }void build( int &now, int l, int r ) {now = ++ cnt;if( l == r ) { t[now].fa = l, t[now].ans = dis[l], t[now].h = 0; return; }int mid = ( l + r ) >> 1;build( t[now].l, l, mid );build( t[now].r, mid + 1, r ); }int query( int now, int l, int r, int pos ) {if( l == r ) return now;int mid = ( l + r ) >> 1;if( pos <= mid ) return query( t[now].l, l, mid, pos );else return query( t[now].r, mid + 1, r, pos ); }int find( int rt, int x ) {int now = query( rt, 1, n, x );while( t[now].fa ^ x ) {x = t[now].fa;now = query( rt, 1, n, x );}return now; }void modify( int &now, int lst, int l, int r, int pos, int New_fa ) {t[now = ++ cnt] = t[lst];if( l == r ) { t[now].fa = New_fa; return; }int mid = ( l + r ) >> 1;if( pos <= mid ) modify( t[now].l, t[lst].l, l, mid, pos, New_fa );else modify( t[now].r, t[lst].r, mid + 1, r, pos, New_fa ); }void update( int &now, int lst, int l, int r, int pos, int ans ) {t[now = ++ cnt] = t[lst];if( l == r ) { t[now].ans = ans; return; }int mid = ( l + r ) >> 1;if( pos <= mid ) update( t[now].l, t[lst].l, l, mid, pos, ans );else update( t[now].r, t[lst].r, mid + 1, r, pos, ans ); }void modify( int now, int l, int r, int pos ) {if( l == r ) { t[now].h ++; return; }int mid = ( l + r ) >> 1;if( pos <= mid ) modify( t[now].l, l, mid, pos );else modify( t[now].r, mid + 1, r, pos ); }signed main() { // freopen( "return.in", "r", stdin ); // freopen( "return.out", "w", stdout );int T;scanf( "%lld", &T );while( T -- ) {scanf( "%lld %lld", &n, &m );for( int i = 1;i <= n;i ++ ) G[i].clear();for( int i = 1, u, v, l, a;i <= m;i ++ ) {scanf( "%lld %lld %lld %lld", &u, &v, &l, &a );G[u].push_back( { u, v, l, a } );G[v].push_back( { u, u, l, a } );E[i] = { u, v, l, a };high[i] = a;}dijkstra();sort( E + 1, E + m + 1, []( edge x, edge y ) { return x.h < y.h; } );sort( high + 1, high + m + 1 );int now = m;m = unique( high + 1, high + m + 1 ) - high - 1;cnt = 0;build( root[m + 1], 1, n );for( int i = m;i;i -- ) {root[i] = root[i + 1];while( E[now].h == high[i] ) {int u = find( root[i], E[now].u );int v = find( root[i], E[now].v );if( t[u].fa ^ t[v].fa ) {if( t[u].h < t[v].h ) swap( u, v ); //并查集按(秩)樹高合并modify( root[i], root[i], 1, n, t[v].fa, t[u].fa );if( t[v].ans < t[u].ans )update( root[i], root[i], 1, n, t[u].fa, t[v].ans );//新加入的v帶來更小的新答案if( t[u].h == t[v].h )modify( root[i], 1, n, t[u].fa );}now --;}}scanf( "%lld %lld %lld", &Q, &K, &S );int v, p, lastans = 0;while( Q -- ) {scanf( "%lld %lld", &v, &p );v = ( v + K * lastans - 1 ) % n + 1;p = ( p + K * lastans ) % ( S + 1 );p = upper_bound( high + 1, high + m + 1, p ) - high;printf( "%lld\n", lastans = t[find( root[p], v )].ans );}}return 0; }

solution2

將邊權按海拔高度從大到小排序，然后kruskal重構樹，顯然這個重構樹是小根堆

所以如果詢問海拔小于詢問點某個祖先的權值，意味著這個祖先的子樹內所有點都是可以開車到達的，那么其實就是詢問這個祖先子樹內的點到$1$的最短路

怎么找個祖先，就可以用倍增來找了

code

#include <queue> #include <cstdio> #include <vector> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define maxn 400005 #define int long long #define Pair pair < int, int > vector < int > G[maxn]; priority_queue < Pair, vector < Pair >, greater < Pair > > q; struct node { int u, v, h; }E[maxn]; int head[maxn], to[maxn << 1], nxt[maxn << 1], len[maxn << 1]; int first[maxn], End[maxn], enxt[maxn]; int T, n, m, cnt, cntt; int dis[maxn], fa[maxn], val[maxn], ans[maxn]; int f[maxn][20];void addedge( int u, int v, int w ) {to[cnt] = v, nxt[cnt] = head[u], len[cnt] = w, head[u] = cnt ++; }int find( int x ) { return fa[x] == x ? x : fa[x] = find( fa[x] ); }void dijkstra() {for( int i = 1;i <= n;i ++ ) dis[i] = 1e18;q.push( make_pair( dis[1] = 0, 1 ) );while( ! q.empty() ) {int now = q.top().second, d = q.top().first; q.pop();if( d ^ dis[now] ) continue;for( int i = head[now];~ i;i = nxt[i] )if( dis[to[i]] > dis[now] + len[i] ) {dis[to[i]] = dis[now] + len[i];q.push( make_pair( dis[to[i]], to[i] ) );}}for( int i = 1;i <= n;i ++ ) ans[i] = dis[i]; }void addedge( int u, int v ) {End[cntt] = v, enxt[cntt] = first[u], first[u] = cntt ++; }void kruskal() {sort( E + 1, E + m + 1, []( node x, node y ) { return x.h > y.h; } );for( int i = 1;i <= n;i ++ ) fa[i] = i;cnt = n;for( int i = 1, tot = 0;i <= m;i ++ ) {int u = E[i].u, v = E[i].v;int fu = find( u ), fv = find( v );if( fu ^ fv ) {++ cnt;val[cnt] = E[i].h;fa[cnt] = fa[fu] = fa[fv] = cnt;addedge( cnt, fu );addedge( cnt, fv );tot ++;if( tot == n - 1 ) break;}} }void dfs( int u ) {for( int i = 1;i < 20;i ++ )f[u][i] = f[f[u][i - 1]][i - 1];for( int i = first[u];~ i;i = enxt[i] ) {int v = End[i];f[v][0] = u;dfs( v );ans[u] = min( ans[u], ans[v] );} }void read( int &x ) {x = 0;char s = getchar();while( s < '0' or s > '9' ) s = getchar();while( '0' <= s and s <= '9' ) x = ( x << 1 ) + ( x << 3 ) + ( s ^ 48 ), s = getchar(); }signed main() {freopen( "return.in", "r", stdin );freopen( "return.out", "w", stdout );read( T );while( T -- ) {read( n ), read( m );cnt = cntt = 0;for( int i = 1;i <= n;i ++ ) {head[i] = first[i] = first[i + n] = -1;for( int j = 0;j < 20;j ++ ) f[i][j] = 0;} for( int i = n + 1;i <= ( n << 1 );i ++ ) G[i].clear();for( int i = 1, u, v, l, h;i <= m;i ++ ) {read( u ), read( v ), read( l ), read( h );E[i] = { u, v, h };addedge( u, v, l );addedge( v, u, l );}dijkstra();kruskal();for( int i = n + 1;i <= cnt;i ++ ) ans[i] = 1e18;dfs( cnt );int Q, K, S, v, p, lst = 0;read( Q ), read( K ), read( S );while( Q -- ) {read( v ), read( p );v = ( v + K * lst - 1 ) % n + 1;p = ( p + K * lst ) % ( S + 1 );for( int i = 19;~ i;i -- )if( val[f[v][i]] > p ) v = f[v][i];printf( "%lld\n", lst = ans[v] );}}return 0; }

總結

以上是生活随笔為你收集整理的[NOI2018] 归程（线段树维护并查集的可持久化/kruskal重构树，倍增+dijkstra最短路）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。