LOJ2718
BZOJ5415
洛谷P4768
Rank3+Rank1無壓力
BZOJ最初還不是一道權(quán)限題...

Update 2019.1.5
UOJ上被hack了....好像是純一條鏈的數(shù)據(jù)過不了，不管了....現(xiàn)在不想改。

容易想到按高度Kruskal重構(gòu)樹+預(yù)處理到點(diǎn)1的距離dis。
建一棵最大生成樹，如果隨便建的話，如果非樹邊能走，整棵樹都能走答案當(dāng)然是0...；如果有些樹邊不能走，那么可走范圍被限制在了某個連通塊。
然而被限制在某個連通塊和圖(還要暴力，難道樹分塊?)沒什么區(qū)別，所以我們可以讓生成樹邊的高度由葉子向上遞減，這樣每次詢問 找到深度最小的可行點(diǎn)后，答案就是其子樹dis最小值(樹形態(tài)顯然不會影響什么)。
就是在Kruskal合并兩個集合時，新建一個節(jié)點(diǎn)作為兩集合的并的代表節(jié)點(diǎn)，最低高度mn為這條邊權(quán)(當(dāng)然不會比兩集合中的大)，dis為兩集合dis的min。新樹葉子節(jié)點(diǎn)即為原所有節(jié)點(diǎn)。

昨天一時zz怎么就覺得Kruskal不對呢。。

//8079ms 51424K(LOJ) //洛谷 4860ms 50.49MB + 4392ms 50.33MB #include <queue> #include <cstdio> #include <cctype> #include <cstring> #include <algorithm> //#define gc() getchar() #define MAXIN 400000 #define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++) #define mp std::make_pair #define pr std::pair<int,int> const int N=2e5+5,M=8e5+5,INF=0x7fffffff;int n,m,tot,Enum,H[N],nxt[M],to[M],len[M],dis[N],fa[N<<1][19],mn[N<<1],anc[N<<1],Ans[N<<1]; std::priority_queue<pr> q; char IN[MAXIN],*SS=IN,*TT=IN; struct Edge {int fr,to,h;Edge() {}Edge(int fr,int to,int h):fr(fr),to(to),h(h) {}bool operator <(const Edge &x)const{return h>x.h;} }e[M>>1];inline int read() {int now=0;register char c=gc();for(;!isdigit(c);c=gc());for(;isdigit(c);now=now*10+c-'0',c=gc());return now; } inline void AddEdge(int _h,int w,int u,int v) {to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum, len[Enum]=w;to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum, len[Enum]=w;e[Enum>>1]=Edge(u,v,_h); } void Dijkstra() {static bool vis[N];memset(dis,0x3f,sizeof dis), memset(vis,0,sizeof vis);dis[1]=0, q.push(mp(0,1));while(!q.empty()){int x=q.top().second; q.pop();if(vis[x]) continue;vis[x]=1;for(int v,i=H[x]; i; i=nxt[i])if(dis[v=to[i]]>dis[x]+len[i])dis[v]=dis[x]+len[i], q.push(mp(-dis[v],v));} } int Get_fa(int x){return x==anc[x]?x:anc[x]=Get_fa(anc[x]); } void Kruskal() {for(int i=1; i<=n; ++i) anc[i]=i, Ans[i]=dis[i];int m=Enum>>1; std::sort(e+1,e+1+m);for(int r1,r2,k=1,i=1; i<=m; ++i){if((r1=Get_fa(e[i].fr))==(r2=Get_fa(e[i].to))) continue;anc[r1]=anc[r2]=fa[r1][0]=fa[r2][0]=++tot, anc[tot]=fa[tot][0]=tot/*!*/;//清空新建的fa[tot]！(可能作為根節(jié)點(diǎn))mn[tot]=e[i].h, Ans[tot]=std::min(Ans[r1],Ans[r2]);if(++k==n) break;} } void Init_ST() {for(int i=1; i<=18; ++i)for(int x=1; x<=tot; ++x) fa[x][i]=fa[fa[x][i-1]][i-1]; } inline int Solve(int p,int ht) {for(int i=18; ~i; --i)if(mn[fa[p][i]]>ht) p=fa[p][i];return Ans[p]; }int main() { // freopen("return.in","r",stdin); // freopen("return.out","w",stdout);int Case=read();while(Case--){Enum=0, memset(H,0,sizeof H);tot=n=read(), m=read();while(m--) AddEdge(read(),read(),read(),read());Dijkstra(), Kruskal(), Init_ST();int Q=read(),K=read(),S=read(),ans=0,pos,ht;if(K) while(Q--)pos=(read()+ans-1)%n+1,ht=(read()+ans)%(S+1),printf("%d\n",ans=Solve(pos,ht));else while(Q--)pos=read(),ht=read(),printf("%d\n",Solve(pos,ht));}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/SovietPower/p/9334873.html

總結(jié)

以上是生活随笔為你收集整理的LOJ.2718.[NOI2018]归程(Kruskal重构树 倍增)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。