NOI的签到题，可怜我在家打了一下午才搞了80分。
分点来讲吧～
这6个点有两种做法：
法1：最短路。
这6个点都是离线的，而且只有一种海拔，所以直接最短路。
跑完之后，直接判断海拔与水位，输出即可。
不过这些分也并不好拿，spfa会被卡，要用堆优化dijsktra。
法2：离线排序+并查集。
其实这个暴力思想就是正解思想了，很好想到的。
首先跑个最短路求一下1号点到所有点的距离，按照边权从大到小排序，对于询问也按照水位线从大到小排一下序。
显然，当一条边加入以后，就不可能再删除，因为水位线只会慢慢降低。
这样这个问题就可以转化成，当前询问下，如果把所有大于当前水位线的边加入图中，那么从起点出发，求它所能到达的点中与1号点距离最小的点即可。
加边时用并查集维护一下即可：
即对于两个点a，b在并查集中的祖先x，y，如果dis[x]>dis[y]，则令fa[x]=y。
这样并查集在查询时，就可以以常数的复杂度找到当前询问下的答案。注意加边是在一个查询开始前，将所有海拔大于水位线的边加进去。
这里我们可以考虑倍增。
预处理3个ST表：dpt[][]，num[][]，xiao[][]
分别表示从x点跳\(2^j\)步，从x到向上\(2^j\)个点的花费，最后是从x到向上\(2^j\)个点中海拔最小的点。
所以算法也很简单，先调到海拔最小的点，然后再倍增求花费。
当然也可以用之前讲的离线排序+并查集。
直接按上面说的离线并查集即可。
离线并查集不管用了？别担心。
因为数据范围小，直接在线，每次询问用一个新的并查集维护。
反正能过。
其实上面讲的也差不多了。
上面的算法最接近正解的就两种：
第1种：离线+一个并查集。这样可以处理离线的大数据点。
第2种：在线+很多并查集。这样可以处理在线的小数据点。
结合起来，大概有点可持久化的味道了。
没错，这一题就是要用到一种叫可持久化并查集的数据结构。
具体算法应该是kruskal重构树，这个听起来就很高级的算法。
但当我们使用 kruskal重构树的时候，对于每次找出的不同的两个连通块的祖先，我们都新建一个点作为两个祖先的父亲，并将当前边的边权转化为新点的点权。
然而，路径压缩的时候会让我们丢失这种辛辛苦苦创造的树的形状。。。
因此我们需要在使用并查集维护连通性的同时使用二叉树来维护树的形状。
这样维护出来的树就是 kruskal重构树。
用kruskal重构树+排序可持久化并查集的做法，就可以A了这道T辣～
#include <bits/stdc++.h>
using namespace std;
typedef pair<long long,int> Pair;
void read(int &aa)
{
aa=0;char c=getchar();bool f=0;
while (c>'9'||c<'0') {if (c=='-') f=1;c=getchar();}
while (c>='0'&&c<='9')
aa=(aa<<3)+(aa<<1)+(c^48),c=getchar();
(f)&&(aa=-aa);
}
const int N=800020;
int n,m,q,k,s;
struct Edge {
int next,cost,high,to;
}e[N<<2];
int last[N],spfaflag;
void add(int x,int y,int c,int h)
{
e[++last[0]].to=y;
e[last[0]].cost=c;e[last[0]].next=last[x];
e[last[0]].high=h;last[x]=last[0];
}
int vis[N];
long long dis[N];
queue <int> Q;
priority_queue< Pair,vector<Pair>,greater<Pair> >que;
void spfa()
{
while (!Q.empty()) Q.pop();
for (int i=1;i<=n;++i) dis[i]=2e9+1;
memset(vis,0,sizeof(vis));
vis[1]=1;Q.push(1);dis[1]=0;
while (!Q.empty()) {
int x=Q.front();Q.pop();vis[x]=0;
for (int i=last[x];i;i=e[i].next) {
int y=e[i].to,c=e[i].cost;
if (dis[y]>dis[x]+c) {
dis[y]=dis[x]+c;
if (!vis[y]) vis[y]=1,Q.push(y);
}
}
}
}
void dijsktra()
{
while (!que.empty()) que.pop();
for (int i=1;i<=n;++i) dis[i]=2e9+1;
memset(vis,0,sizeof(vis));
dis[1]=0;
que.push(make_pair(dis[1],1));
while (!que.empty()) {
Pair now=que.top();que.pop();
if (vis[now.second]) continue;
vis[now.second]=1;
for (int i=last[now.second];i;i=e[i].next)
if (dis[now.second]+e[i].cost<dis[e[i].to]) {
dis[e[i].to]=dis[now.second]+e[i].cost;
if (!vis[e[i].to]) que.push(make_pair(dis[e[i].to],e[i].to));
}
}
}
int bian[N],gao[N];
void chain()
{
int ed,pp,chainflag;
long long ans,preans=0;
read(q);read(k);read(s);
for (int i=1;i<=q;++i) {
chainflag=ans=0;
read(ed);read(pp);
ed=(ed+k*preans-1)%n+1;
pp=(pp+k*preans)%(s+1);
for (int t=ed;t>1;--t)
if (chainflag||gao[t]<=pp)
ans+=bian[t],chainflag=1;
printf("%lld\n",ans);
preans=ans;
}
}
int dep[N],dpt[N][33],xiao[N][33],num[N][33];
void dfs(int x,int d)
{
dep[x]=d;
for (int i=last[x];i;i=e[i].next) {
int y=e[i].to;
if (!dep[y]) {
dpt[y][0]=x;
xiao[y][0]=e[i].high;
num[y][0]=e[i].cost;
dfs(y,d+1);
}
}
}
void init()
{
for (int j=1;j<=24;++j)
for (int i=1;i<=n;++i) {
dpt[i][j]=dpt[dpt[i][j-1]][j-1];
xiao[i][j]=min(xiao[i][j-1],xiao[dpt[i][j-1]][j-1]);
num[i][j]=num[i][j-1]+num[dpt[i][j-1]][j-1];
}
}
int zuo(int x,int gaodu)
{
int ans=0;
for (int j=24;j>=0;--j) {
if (xiao[x][j]>gaodu&&dpt[x][j])
x=dpt[x][j];
}
if (x!=1) {
for (int j=24;j>=0;--j)
if (dpt[x][j])
ans+=num[x][j],x=dpt[x][j];
return ans;
}
return 0;
}
void tree()
{
int ed,pp;
dfs(1,1);init();
read(q);read(k);read(s);
int ans,preans=0;
for (int i=1;i<=q;++i) {
read(ed);read(pp);
ed=(ed+k*preans-1)%n+1;
pp=(pp+k*preans)%(s+1);ans=zuo(ed,pp);
printf("%d\n",ans);preans=ans;
}
}
struct Line {
int from,to,cost,high;
}line[N<<1];
struct ask {
int shui,id,v,res;
}wen[N];
int baba[N];
bool pai1(ask t1,ask t2)
{
return t1.shui>t2.shui;
}
bool pai2(Line t1,Line t2)
{
return t1.high>t2.high;
}
bool pai3(ask t1,ask t2)
{
return t1.id<t2.id;
}
int find(int x)
{
return x!=baba[x]?baba[x]=find(baba[x]):x;
}
void unionset(int x,int y)
{
int u=find(x),v=find(y);
if (u==v) return;
if (dis[u]>dis[v]) baba[u]=v;
else baba[v]=u;
}
void outline()
{
for (int i=1;i<=q;++i) {
read(wen[i].v);read(wen[i].shui);
wen[i].id=i;
}
sort(&wen[1],&wen[1+q],pai1);
sort(&line[1],&line[1+m],pai2);
for (int i=1;i<=n;++i) baba[i]=i;
int now=1;
for (int i=1;i<=q;++i) {
while (now<=m&&line[now].high>wen[i].shui)
unionset(line[now].from,line[now].to),++now;
wen[i].res=dis[find(wen[i].v)];
}
sort(wen+1,wen+1+q,pai3);
for (int i=1;i<=q;++i) printf("%d\n",wen[i].res);
}
void navi_inline()
{
int lastans=0,instead;
sort(line+1,line+1+m,pai2);
for (int j=1;j<=q;++j) {
for (int i=1;i<=n;++i) baba[i]=i;
int now=1;
read(instead);
int v=(instead+k*lastans-1)%n+1;
read(instead);
int p=(instead+k*lastans)%(s+1);
while (now<=m&&line[now].high>p)
unionset(line[now].from,line[now].to),++now;
lastans=dis[find(v)];
printf("%d\n",lastans);
}
}
bool cmp(Line t1,Line t2)
{
return t1.high>t2.high;
}
Line line2[N<<1];
int fa[N],ceng[N],tiao[N][25];
struct eeee {
int to,next;
}ee[N<<1];
int head[N];
void jia(int x,int y)
{
ee[++head[0]].to=y;ee[head[0]].next=head[x];
head[x]=head[0];
}
void shensou(int x,int pa)
{
ceng[x]=ceng[pa]+1,tiao[x][0]=pa;
for (int i=1;i<=24;++i)
tiao[x][i]=tiao[tiao[x][i-1]][i-1];
for (int i=head[x];i;i=ee[i].next) {
int y=ee[i].to;
shensou(y,x);
line2[x].cost=min(line2[x].cost,line2[y].cost);
}
}
int xunwenta(int x,int y)
{
for (int i=24;i>=0;--i)
if (ceng[x]-(1<<i)>0&&line2[tiao[x][i]].high>y)
x=tiao[x][i];
return line2[x].cost;
}
int find2(int x)
{
return x==fa[x]?x:fa[x]=find2(fa[x]);
}
void zhengjie_wo_wu_di_la_hahaha_kruskal()
{
int tott=0,cntt=n;
for (int i=1;i<=(n<<1);++i) fa[i]=i;
sort(line+1,line+m+1,cmp);
for (int i=1;i<=m;++i) {
int u=line[i].from,v=line[i].to;
int fx=find2(u),fy=find2(v);
if (fx!=fy) {
jia(++cntt,fx);
jia(cntt,fy);
fa[fx]=cntt;
fa[fy]=cntt;
line2[cntt].high=line[i].high;
++tott;
}
if (tott+1==n) break;
}
int lastans=0;
shensou(cntt,0);
int tttt;
while (q--) {
read(tttt);
int x=(k*lastans+tttt-1)%n+1;
read(tttt);
int y=(k*lastans+tttt)%(s+1);
printf("%d\n",lastans=xunwenta(x,y));
}
}
int main()
{
int T,x,y,c,h;read(T);
while (T--) {
memset(last,0,sizeof(last));
memset(gao,0,sizeof(gao));
memset(bian,0,sizeof(bian));
memset(dep,0,sizeof(dep));
memset(dpt,0,sizeof(dpt));
memset(xiao,0,sizeof(xiao));
memset(num,0,sizeof(num));
memset(head,0,sizeof(head));
memset(tiao,0,sizeof(tiao));
read(n);read(m);bool flag=1;
int pre=0,mp=2;
for (int i=1;i<=m;++i) {
read(x);read(y);read(c);read(h);
gao[y]=h;bian[y]=c;
if (x+1!=y) flag=0;
if (pre!=h) --mp,pre=h;
add(x,y,c,h);add(y,x,c,h);
line[i].from=x;line[i].to=y;
line[i].cost=c;line[i].high=h;
}
if (mp==1) {
int ed,pp;
read(q);read(k);read(s);dijsktra();
for (int i=1;i<=q;++i) {
spfaflag=0;
read(ed);read(pp);
ed=(ed-1)%n+1;pp=pp%(s+1);
if (pp>=pre) spfaflag=1;
printf("%lld\n",!spfaflag?dis[1]:dis[ed]);
}
continue;
}
if (m+1==n) {
if (flag) chain();
else tree();
continue;
}
read(q);read(k);read(s);
if (!k) {
dijsktra();
outline();
continue;
}
if (k&&n<=1500) {
dijsktra();
navi_inline();
continue;
}
for (int i=n+1;i<=(n<<1);++i)
line2[i].cost=0x3f3f3f3f;
dijsktra();
for (int i=1;i<=n;++i)
line2[i].cost=dis[i];
zhengjie_wo_wu_di_la_hahaha_kruskal();
}
return 0;
}原文：https://www.cnblogs.com/fushao2yyj/p/9513166.html