「NOI2018」归程

发表于 更新于 分类于

题目链接：https://loj.ac/problem/2718。

感觉这更像是个算法学习笔记。。。

介绍一个叫$\rm Kruskal$重构树的东西，这个东西可以很方便的处理出，从给定的点$x$出发，只经过边权$\leqslant s$的边能到的点是哪些。

首先很显然，如果我们把最小生成树搞出来，其他边删掉，答案还是不会改变，因为如果可以通过其他边到另外的点，最小生成树就可以利用这些边变得更小。

那么如何利用这个东西呢，考虑用$\rm Kruskal$算法求最小生成树的的时候，假设当前这条边能合并左右两个块，我们就新建一个点出来，连向左右两边重构树的根节点，然后把这个点作为合并后的块的重构树的根节点。

那么最后我们会得到一颗$2n-1$个点的树，其中所有的原来就有的点都是叶子，非叶子节点都是新建的点，并且是二叉树。

如果我们每次新建点的时候把边权赋给这个点作为点权，那么显然可以知道，从$x$出发只经过边权$\leqslant s$的边能到的点 就是 从$x$每次往父亲跳，直到父亲点权大于$x$，此时当前点子树里的所有点。感觉我表达能力好差

那么这题就差不多做完了，一开始跑个最短路，然后把重构树建出来，记一下子树里叶子离$1$号点距离最小的是多少，每次倍增跳一下就好了。

复杂度$O(n\log n)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include<bits/stdc++.h>
using namespace std;

void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}

void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double
#define ll long long 

#define pii pair<int,int >
#define vec vector<int >

#define pb push_back
#define mp make_pair
#define fr first
#define sc second

#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)

const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;

int n,m,q,dis[maxn],cnt,val[maxn],id[maxn],f[maxn][20],tot,head[maxn];
struct edge{int to,nxt,w;}e[maxn<<1];

void ins(int u,int v,int w) {e[++tot]=(edge){v,head[u],w},head[u]=tot;}

struct info {int u,v,w;}a[maxn];

int cmp(info x,info y) {return x.w<y.w;}

struct dsu {
    int fa[maxn];
    void init() {for(int i=1;i<=n;i++) fa[i]=i;}
    int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);}
}s;

void get_dis() {
    priority_queue<pair<int,int > > q;
    memset(dis,63,sizeof dis);
    q.push(mp(0,1));dis[1]=0;
    while(!q.empty()) {
        int w=-q.top().fr,x=q.top().sc;q.pop();
        if(dis[x]<w) continue;
        for(int i=head[x];i;i=e[i].nxt)
            if(dis[e[i].to]>dis[x]+e[i].w)
                dis[e[i].to]=dis[x]+e[i].w,q.push(mp(-dis[e[i].to],e[i].to));
    }
}

void solve() {
    read(n),read(m);s.init();cnt=n;
    for(int i=1,u,v,l,aa;i<=m;i++) {
        read(u),read(v),read(l),read(aa);
        ins(u,v,l),ins(v,u,l);
        a[i]=(info){u,v,-aa};
    }
    get_dis();
    for(int i=1;i<=n;i++) id[i]=i;
    sort(a+1,a+m+1,cmp);
    for(int i=1;i<=m;i++) {
        int u=s.find(a[i].u),v=s.find(a[i].v);
        if(u!=v) {
            s.fa[u]=v;
            val[++cnt]=a[i].w;
            f[id[u]][0]=f[id[v]][0]=cnt;
            dis[cnt]=min(dis[id[u]],dis[id[v]]);
            id[v]=cnt;
        }
    }
    for(int i=1;i<=18;i++) 
        for(int j=1;j<=cnt;j++)
            f[j][i]=f[f[j][i-1]][i-1];
    read(q);int k,s;read(k),read(s);
    int la=0;
    for(int i=1;i<=q;i++) {
        int v,p;read(v),read(p);
        v=(v+k*la-1)%n+1,p=(p+k*la)%(s+1);
        for(int j=18;~j;j--)
            if(f[v][j]&&-val[f[v][j]]>p) v=f[v][j];
        write(la=dis[v]);
    }
}

void clear() {
    memset(head,0,sizeof head);
    tot=0;
}

int main() {
    // freopen("return.in","r",stdin);
    // freopen("return.out","w",stdout);
    int t;read(t);while(t--) solve(),clear();
    return 0;
}