[NOI2018]归程 [Kruskal 重构树]

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

传送门

刚刚学Kruskal重构树就来写这道题, 我都佩服我自己...

不过还好把Kruskal 重构树学会了

https://blog.csdn.net/niiick/article/details/81952126

 

 

---

关于本题, 题意: 将v到1的路径分成两半, v-v的路u的海拔最小的至少为a+1, 求u到1的最小值

以下来自https://blog.csdn.net/niiick/article/details/81138433 

---

#include<bits/stdc++.h>
#define N 400050
#define M N*2
#define LL long long
#define inf 1000000000000000
using namespace std;int first[N],next[M],to[M],w[M],tot;  // Kruskal 重构树的边 & dijstruct Node{int u,v,w;}E[M]; int val[N],f[N][23]; LL Min_dis[N];// Kruskal 重构树
bool cmp(Node a,Node b){return a.w>b.w;}LL dis[N]; // dijsktra
int T,n,m,q,k,s,cnt; LL ans;
int fa[N]; int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}int read(){int cnt=0; char ch=0;while(!isdigit(ch))ch=getchar();while(isdigit(ch))cnt=cnt*10+(ch-'0'),ch=getchar();return cnt;
}void add(int x,int y,int z){next[++tot]=first[x],first[x]=tot,to[tot]=y,w[tot]=z;}
void Init_graph(){memset(first,0,sizeof(first));memset(next,0,sizeof(next));memset(to,0,sizeof(to));memset(w,0,sizeof(w)); tot = 0;
}
void dijsktra(){priority_queue<pair<int,int> >q;for(int i=1;i<=n;i++) dis[i] = inf;dis[1]=0; q.push(make_pair(0,1));while(!q.empty()){int x=q.top().second; q.pop();for(int i=first[x];i;i=next[i]){int t=to[i]; if(dis[t] > dis[x] + w[i]){dis[t] = dis[x] + w[i];q.push(make_pair(-dis[t],t));}}} 
}void Kruskal(){Init_graph();sort(E+1,E+m+1,cmp);cnt = n;for(int i=1;i<=m;i++){int x = E[i].u, y = E[i].v;int fx = find(x), fy = find(y);if(fx!=fy){val[++cnt] = E[i].w;fa[fx] = fa[fy] = cnt;add(cnt,fx,0); add(cnt,fy,0);}}
}void dfs(int u){if(u<=n) Min_dis[u] = dis[u];for(int i=1;i<=20;i++) f[u][i] = f[f[u][i-1]][i-1];for(int i=first[u];i;i=next[i]){int t=to[i]; f[t][0] = u;dfs(t); Min_dis[u] = min(Min_dis[u], Min_dis[t]);}
}
int main(){T=read();while(T--){ Init_graph();memset(f,0,sizeof(f));memset(val,0,sizeof(val));n=read(), m=read();for(int i=1;i<=n*2;i++) fa[i]=i;for(int i=1;i<=m;i++){int x=read(),y=read(),z=read(),a=read();E[i] = (Node){x,y,a}; add(x,y,z); add(y,x,z);}dijsktra();Kruskal(); for(int i=1;i<=n*2;i++) Min_dis[i] = inf;dfs(cnt);q=read(),k=read(),s=read();ans = 0;while(q--){int x=read(),y=read();x = (LL)(x + k* ans -1) % n + 1;y = (LL)(y + k* ans ) % (s+1);for(int i=20;i>=0;i--)if(f[x][i] && val[f[x][i]]>y) x = f[x][i];ans = Min_dis[x];printf("%lld\n",ans);}}return 0;
}

 

这篇关于[NOI2018]归程 [Kruskal 重构树]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---