「NOI2018」 归程 - 最短路+Kruskal重构树+倍增

本文主要是介绍「NOI2018」 归程 - 最短路+Kruskal重构树+倍增，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题面

LuoguP4768

题目大意：给定一张$n$个点$m$条边的无向连通图，每条边带两个权值$l,a$，每次询问给出$v,p$，要求从$v$点开始，可以走边$a>p$的边，路程为0，不能走后，走其他边，路程为$l$，求从$v$开始到$1$的最短路程。部分数据强制在线。

分析

对于每次询问给定的$v,p$，若点$x,y$之间最大边的最小值大于$p$，则$x,y$可以互相到达。于是可以想到构建Kruskal重构树，边权从大到小排序建树。由于这样建树后，对于$v$能到达的节点，肯定在以$v$的一个权值大于$p$且层数最低的祖先的子树中。于是我们可以先跑一遍从$1$开始的最短路，计算每个点到$1$的最短路径，然后对于Kruskal重构树进行一次Dfs，求出每个点的子树中叶子节点的距离最小值。至于找这个祖先，可以用倍增去找。因为这棵树呈一棵小根堆，满足儿子节点的点权一定大于等于父节点的点权（叶子节点除外），故可以用倍增。这样可以做到在线回答。

对于离线的子问题，可以将边按$a$值排序，询问按照$p$值排序，两个指针扫过去，用并查集维护连通以及连通块内到$1$的距离最小值。基于这种思想，就有人想到用可持久化并查集代替普通的并查集做到在线回答。

还有这道题卡SPFA，只能用Djikstra。

代码

只有Kruskal重构树。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int N=200050*2;
const int M=400050;
const int INF=0x3f3f3f3f;
typedef long long LL;
struct Edge {int to,nxt;LL wei;};
struct Array {int x,y;LL w;};
Edge e[M<<1];
Array p[M];
int n,m,f[N][31];
int h[N],cnt,fa[N];
int n_,q,T;
int L[N],R[N],k;
LL v[N],lastans,val[N],len;
bool cmp(Array a,Array b) {return a.w>b.w;}
void Add_Edge(int x,int y,int z) {e[++cnt]=(Edge){y,h[x],z};h[x]=cnt;}
int getf(int x) {return fa[x]==x?x:fa[x]=getf(fa[x]);}
void Clear() {//清空 memset(f,0,sizeof(f));memset(L,0,sizeof(L));memset(R,0,sizeof(R));memset(val,0x3f,sizeof(val));memset(v,0,sizeof(v));memset(h,0,sizeof(h));cnt=lastans=0;
}
int Ex_Kruskal() {//Kruskal重构树 sort(p+1,p+m+1,cmp);int ind=n_,lim=n_*2;for (int i=1;i<=lim;i++) fa[i]=i;for (int i=1;i<=m;i++) {int x=getf(p[i].x),y=getf(p[i].y);if (x!=y) {fa[x]=fa[y]=++ind;L[ind]=x,R[ind]=y;//由于是个二叉树,记录左右儿子就行了 val[ind]=p[i].w;if (ind==n_*2-1) break;}}return ind;
}
struct Node {//Dijkstra LL d;int x;Node(LL d=0,int x=0):d(d),x(x){}
};
bool operator<(const Node&a,const Node&b) {return a.d>b.d;}
LL dis[N];
int vis[N];
void Dijkstra(int s) {fill(dis,dis+N,1e17);dis[s]=0;memset(vis,0,sizeof(vis));priority_queue<Node> q;q.push(Node(0,s));while (!q.empty()) {int x=q.top().x;q.pop();if (vis[x]) continue;vis[x]=1;for (int i=h[x];i;i=e[i].nxt) {int y=e[i].to;if (dis[y]>dis[x]+e[i].wei&&!vis[y]) {dis[y]=dis[x]+e[i].wei;q.push(Node(dis[y],y));}}}
}
void Dfs(int x) {//初始化子树叶子节点到1的最小值 if (!L[x]&&!R[x]) {v[x]=dis[x];return;}f[L[x]][0]=x,f[R[x]][0]=x;Dfs(L[x]),Dfs(R[x]);v[x]=min(v[L[x]],v[R[x]]);
}
int Find(int x,int d) {//倍增找点 for (int i=30;~i;i--)if (f[x][i]&&val[f[x][i]]>d) x=f[x][i];return x;
}
void Read() {//数据读入 scanf("%d%d",&n_,&m);for (int i=1;i<=n_;i++) val[i]=INF;for (int i=1;i<=m;i++) {int u,v,w,l;scanf("%d%d%d%d",&u,&v,&l,&w);p[i]=(Array){u,v,w};Add_Edge(u,v,l);Add_Edge(v,u,l);}scanf("%d%d%lld",&q,&k,&len);
}
void Init() {n=Ex_Kruskal(); Dijkstra(1);Dfs(n);for (int j=1;(1<<j)<=n;j++)//倍增初始化 for (int i=1;i<=n;i++)f[i][j]=f[f[i][j-1]][j-1];
}
void Solve() {//回答 while (q--) {int u;LL d;scanf("%d%lld",&u,&d);u=(u+k*lastans-1)%n_+1;d=(d+k*lastans)%(len+1);printf("%lld\n",lastans=v[Find(u,d)]);}
}
int main() {scanf("%d",&T);while (T--) {Clear();Read();Init();Solve();}return 0;
}

这篇关于「NOI2018」 归程 - 最短路+Kruskal重构树+倍增的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---