[NOI2018]归程

桃扇骨 2023-06-02 11:57 4阅读 0赞

[\[NOI2018\]归程][NOI2018]  
这题我只会离线做法..在线做法的克鲁斯卡尔重构树我虽然会但是...我不会倍增...所以就比较困难,于是暂时先只写了离线做法.  
这个题其实是一个动态的图上的最短路问题.  
从\\(1\\)号点开始跑一遍 Dijkstra,求出到每个节点的最短路  
然后问题就转化成了在开车能到达的点里选择一个dis最小的点  
开车能到达的点用克鲁斯卡尔重构树来维护,每次要查询的就是  
重构树上对应合并节点的子树节点中的dis最小值,寻找对应节点用树上倍增解决  
子树dis最小值随便搞一搞都可以.当然这是正解做法.  
而离线做法就不需要重构树,只需要把询问排一下序.  
然后根据海拔的单调性用加权并查集维护答案就行了.  
\\(Code:\\)

/* 从 1号点开始跑一遍 Dijkstra,求出到每个节点的最短路 然后问题就转化成了在开车能到达的点里选择一个dis最小的点 开车能到达的点用克鲁斯卡尔重构树来维护,每次要查询的就是 重构树上对应合并节点的子树节点中的dis最小值,寻找对应节点用树上倍增解决 子树dis最小值随便搞一搞都可以. But this code is not for online algorithm.Because of my own ability. */ #include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <queue> #define pii pair < int , int > #define rint read<int> using std::pair ; using std::priority_queue ; const int N = 2e5 + 5 ; const int M = 4e5 + 5 ; template < class T > inline T min (T __A , T __B) { return __A < __B ? __A : __B ; } template < class T > inline T read () { T x = 0 , f = 1 ; char ch = getchar () ; while ( ch < '0' || ch > '9' ) { if ( ch == '-' ) f = - 1 ; ch = getchar () ; } while ( ch >= '0' && ch <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ; ch = getchar () ; } return f * x ; } struct edge { int from , to , data , height , next ; } e[(M<<1)] ; struct query { int st , p , order , ans ; } opt[M] ; priority_queue < pii , std::vector < pii > , std::greater < pii > > q ; int T , n , m , head[N] , f[N][2] , dis[N] , Q , k , s , cnt ; inline void Dijkstra (int cur) { memset ( dis , 0x3f , sizeof ( dis ) ) ; dis[cur] = 0 ; q.push ( { dis[cur] , cur } ) ; while ( ! q.empty () ) { int j = q.top ().second ; if ( dis[j] != q.top ().first ) { q.pop () ; continue ; } q.pop () ; for (int i = head[j] ; i ; i = e[i].next) { int t = e[i].to ; if ( dis[t] > dis[j] + e[i].data ) { dis[t] = dis[j] + e[i].data ; q.push ( { dis[t] , t } ) ; } } } return ; } inline int getf (int x) { return f[x][0] == x ? x : ( f[x][0] = getf ( f[x][0] ) ) ; } inline void merge (int u , int v) { int x = getf ( u ) , y = getf ( v ) ; if ( x != y ) { f[y][0] = x ; f[x][1] = min ( f[y][1] , f[x][1] ) ; } return ; } inline void init () { for (int i = 1 ; i <= n ; ++ i) { f[i][0] = i ; f[i][1] = dis[i] ; } return ; } inline bool cmp (edge a , edge b) { return a.height > b.height ; } inline bool CMP (query a , query b) { return a.p > b.p ; } inline void build (int u , int v , int len , int h){ e[++cnt].next = head[u] ; e[cnt].from = u ; e[cnt].to = v ; e[cnt].height = h ; head[u] = cnt ; e[cnt].data = len ; return ; } inline bool Cmp (query a , query b) { return a.order < b.order ; } int main () { T = rint () ; while ( T -- ) { cnt = 0 ; n = rint () ; m = rint () ; memset ( head , 0 , sizeof ( head ) ) ; for (int i = 1 , u , v , l , h ; i <= m ; ++ i) { u = rint () ; v = rint () ; l = rint () ; h = rint () ; build ( u , v , l , h ) ; build ( v , u , l , h ) ; } Dijkstra ( 1 ) ; init () ; Q = rint () ; k = rint () ; s = rint () ; for (int i = 1 , u , v ; i <= Q ; ++ i) { u = rint () ; v = rint () ; opt[i].st = ( u - 1 ) % n + 1 ; opt[i].p = v % ( s + 1 ) ; opt[i].order = i ; } std::sort ( e + 1 , e + cnt + 1 , cmp ) ; std::sort ( opt + 1 , opt + Q + 1 , CMP ) ; for (int i = 1 , last = 1 ; i <= Q ; ++ i) { for (int j = last ; e[j].height > opt[i].p && j <= cnt ; ++ j) { merge ( e[j].from , e[j].to ) ; last = j ; if ( e[j].height <= opt[i].p ) break ; } opt[i].ans = f[getf(opt[i].st)][1] ; } std::sort ( opt + 1 , opt + Q + 1 , Cmp ) ; for (int i = 1 ; i <= Q ; ++ i) printf ("%d\n" , opt[i].ans ) ; } return 0 ; }

\\(Updated on 9.3:\\)  
满分思路上面说啦,时隔12天,我终于\\(AC\\)了这道题,哭哭~  
\\(Code:\\)

#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <string> #include <vector> #include <queue> #include <cmath> #include <ctime> #include <map> #include <set> #define MEM(x,y) memset ( x , y , sizeof ( x ) ) #define rep(i,a,b) for (int i = a ; i <= b ; ++ i) #define per(i,a,b) for (int i = a ; i >= b ; -- i) #define pii pair < int , int > #define X first #define Y second #define rint read<int> #define int long long #define pb push_back using std::set ; using std::pair ; using std::max ; using std::min ; using std::priority_queue ; using std::vector ; using std::swap ; using std::sort ; using std::unique ; using std::greater ; template < class T > inline T read () { T x = 0 , f = 1 ; char ch = getchar () ; while ( ch < '0' || ch > '9' ) { if ( ch == '-' ) f = - 1 ; ch = getchar () ; } while ( ch >= '0' && ch <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ; ch = getchar () ; } return f * x ; } const int N = 4e5 + 100 ; struct edge { int to , next , ht , data , pre ; bool friend operator < (edge a , edge b) { return a.ht > b.ht ; } } e[(N<<1)] ; vector < int > G[N] ; priority_queue < pii , vector < pii > , greater < pii > > q ; int T , n , m , g[(N<<1)] , cnt , Q , K , s , deep[(N<<1)] ; int head[(N<<1)] , tot , dis[(N<<1)] , val[(N<<1)] , num ; int minn[(N<<1)] , f[32][(N<<1)] ; inline void build (int u , int v , int w , int h) { e[++tot].next = head[u] ; e[tot].to = v ; e[tot].pre = u ; e[tot].ht = h ; e[tot].data = w ; head[u] = tot ; return ; } inline void Dijkstra (int cur) { while ( ! q.empty () ) q.pop () ; dis[cur] = 0 ; q.push ( { dis[cur] , cur } ) ; while ( ! q.empty () ) { int j = q.top ().Y ; if ( dis[j] != q.top ().X ) { q.pop () ; continue ; } q.pop () ; for (int i = head[j] ; i ; i = e[i].next) { int k = e[i].to ; if ( dis[k] > dis[j] + e[i].data ) { dis[k] = dis[j] + e[i].data ; q.push ( { dis[k] , k } ) ; } } } return ; } inline int getf (int x) { return g[x] == x ? x : g[x] = getf ( g[x] ) ; } inline void Kruskal () { rep ( i , 1 , ( n << 1 ) ) g[i] = i ; num = 0 ; rep ( i , 1 , tot ) { int u = getf ( e[i].pre ) , v = getf ( e[i].to ) ; if ( u != v ) { ++ cnt ; ++ num ; val[cnt] = e[i].ht ; G[cnt].pb ( u ) ; G[cnt].pb ( v ) ; G[u].pb ( cnt ) ; G[v].pb ( cnt ) ; g[cnt] = g[u] = g[v] = cnt ; } if ( num >= n - 1 ) break ; } return ; } inline void dfs (int cur , int anc , int dep) { f[0][cur] = anc ; deep[cur] = dep ; minn[cur] = dis[cur] ; for (int i = 1 ; ( 1 << i ) <= dep ; ++ i) f[i][cur] = f[i-1][f[i-1][cur]] ; for (int k : G[cur] ) { if ( k == anc ) continue ; dfs ( k , cur , dep + 1 ) ; minn[cur] = min ( minn[cur] , minn[k] ) ; } return ; } inline int getp (int x , int height) { int k = log2 ( deep[x] ) ; for (int i = k ; i >= 0 ; -- i) if ( val[f[i][x]] > height && f[i][x] != 0 ) x = f[i][x] ; return x ; } signed main (int argc , char * argv[] ) { T = rint () ; while ( T -- ) { MEM ( dis , 0x7f ) ; n = rint () ; m = rint () ; MEM ( e , 0 ) ; MEM ( head , 0 ) ; tot = 0 ; cnt = n ; rep ( i , 1 , ( n << 1 ) ) G[i].clear () ; MEM ( f , 0 ) ; rep ( i , 1 , m ) { int u = rint () , v = rint () , w = rint () , h = rint () ; build ( u , v , w , h ) ; build ( v , u , w , h ) ; } Dijkstra ( 1 ) ; sort ( e + 1 , e + tot + 1 ) ; Kruskal () ; Q = rint () ; K = rint () ; s = rint () ; dfs ( cnt , 0 , 1 ) ; int lastans = 0 ; while ( Q -- ) { int p = rint () , h = rint () ; p = ( p + K * lastans - 1 ) % n + 1 ; h = ( h + K * lastans ) % ( s + 1 ) ; lastans = minn[getp(p,h)] ; printf ("%lld\n" , lastans ) ; } } system ("pause") ; return 0 ; }

转载于:https://www.cnblogs.com/Equinox-Flower/p/11402227.html

[NOI2018]: https://www.luogu.org/problem/P4768