[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
" , 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
" , lastans ) ;
}
}
system ("pause") ; return 0 ;
}