NOI 2018 Day1 T1 归程（Kruskal重构树/可持久化并查集+DIJ）
Posted On 2018年10月16日
Description
Solution
- Kruskal重构树：考虑将边权排序建立关于海拔的最大生成树，合并两个块时并将该边映射为重构树上的一个点，点权为该边海拔，那么在查询点v时，倍增找到满足海拔限制的离根最近的点（因为在重构树上非叶点权从根节点至任意叶节点递增，该点满足海拔限制则该点子树必定满足），查询子树dist最小值即可,复杂度\(O(nlogn)\)
|
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 |
#include <iostream> #include <cstdio> #include <queue> #include <cstring> #include <bitset> #include <algorithm> using namespace std; typedef int ll; inline int read() { int f=1,k=0;char c=getchar(); while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar(); return k*f; } const int maxn=800000+11,maxm=800000+7,up=19; struct mc{int too,nxt,h,len;}e[maxm<<1],co[maxn<<1]; struct zmc{int a,b,h,len;}store[maxm]; inline bool cmp(const zmc&a,const zmc&b){return a.h>b.h;} int last[maxn],fa[maxn],head[maxm],f[maxn][20],dep[maxm],h[maxm],tot; int dist[maxn]; bitset<maxn>vis; int gf(const int x){return fa[x]==x?x:fa[x]=gf(fa[x]);} inline void add(const int a,const int b,const int h) { co[++tot]=(mc){b,head[a],h,0};head[a]=tot; co[++tot]=(mc){a,head[b],h,0};head[b]=tot; } inline bool clear() { vis.reset(); tot=0; memset(head,0,sizeof(head)); memset(f,0,sizeof(f)); memset(last,0,sizeof(last)); return 1; } priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > >q; inline void dij() { memset(dist,0x3f,sizeof(dist)); dist[1]=0; q.push(make_pair(0,1)); while (!q.empty()) { int cur=q.top().second;q.pop(); if (vis[cur])continue;vis[cur]=1; for (int i=last[cur];i;i=e[i].nxt) if (dist[e[i].too]>dist[cur]+e[i].len) dist[e[i].too]=dist[cur]+e[i].len, q.push(make_pair(dist[e[i].too],e[i].too)); } } void dfs(const int cur,const int fa) { for (int i=1;i<=up;i++)f[cur][i]=f[f[cur][i-1]][i-1]; for (int i=head[cur];i;i=co[i].nxt) if (co[i].too!=fa) dep[co[i].too]=dep[cur]+1,f[co[i].too][0]=cur, dfs(co[i].too,cur), dist[cur]=min(dist[cur],dist[co[i].too]); } inline ll query(int v,const int H) { for (int i=up;i>=0;i--) if (dep[v]-(1<<i)>0&&h[f[v][i]]>H)v=f[v][i]; return dist[v]; } inline void work() { int n=read(),m=read(); for (int i=1;i<=n<<1;i++)fa[i]=i; for (int i=1,a,b;i<=m;i++) a=read(),b=read(), e[i<<1].too=b,e[i<<1].nxt=last[a],last[a]=i<<1, e[i<<1|1].too=a,e[i<<1|1].nxt=last[b],last[b]=i<<1|1, store[i].a=a,store[i].b=b, store[i].len=e[i<<1].len=e[i<<1|1].len=read(), store[i].h=e[i<<1].h=e[i<<1|1].h=read(); dij(); sort(store+1,store+1+m,cmp); int cnt=n; for (int i=1;i<=m;i++) { int x=gf(store[i].a),y=gf(store[i].b); if (x!=y)add(++cnt,x,e[i].h),add(cnt,y,e[i].h),h[cnt]=store[i].h,fa[x]=fa[y]=cnt; if (cnt-n==n-1)break; } dep[cnt]=1; dfs(cnt,0); int q=read(),K=read(),S=read(); ll lastans=0; while (q--) { int v=(read()+K*lastans-1)%n+1,p=(read()+K*lastans)%(S+1); printf("%d\n",lastans=query(v,p)); } } signed main() { freopen("return.in","r",stdin); freopen("return.out","w",stdout); for (int T=read();T;T--)work(),(T-1)&&clear(); } |
- 可持久化并查集：很显然的做法：将海拔从大至小排序，依次加边，查询时二分位置即可,复杂度\(O(nlog^2 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 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 |
#include <iostream> #include <cstdio> #include <queue> #include <cstring> #include <bitset> #include <algorithm> using namespace std; typedef long long ll; inline int read() { int f=1,k=0;char c=getchar(); while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar(); return k*f; } const int maxn=400000+11,maxm=400000+7; struct mc{int too,nxt,h,len;}e[maxm<<1]; struct seg{int val,lc,rc,T,mn,siz;}t[maxm<<7]; struct zmc{int a,b,h,len;}store[maxm]; inline bool cmp(const zmc&a,const zmc&b){return a.h>b.h;} int last[maxn],rt[maxn],tot,T,tt; int dist[maxn],h[maxn]; bitset<maxn>vis; inline bool clear() { vis.reset(); tot=0; memset(last,0,sizeof(last)); return 1; } priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > >q; inline void dij() { memset(dist,0x3f,sizeof(dist)); dist[1]=0; q.push(make_pair(0,1)); while (!q.empty()) { int cur=q.top().second;q.pop(); if (vis[cur])continue;vis[cur]=1; for (int i=last[cur];i;i=e[i].nxt) if (dist[e[i].too]>dist[cur]+e[i].len) dist[e[i].too]=dist[cur]+e[i].len, q.push(make_pair(dist[e[i].too],e[i].too)); } } void update(int&cur,const int l,const int r,const int pos,const int change,const int mn,const int siz,const int T) { if (t[cur].T<T) t[++tot]=t[cur],t[cur=tot].T=T; if (l==r)return (void)(t[cur].val=change,t[cur].mn=mn,t[cur].siz=siz); int mid=(l+r)>>1; if (pos<=mid)update(t[cur].lc,l,mid,pos,change,mn,siz,T); else update(t[cur].rc,mid+1,r,pos,change,mn,siz,T); } int query(const int cur,const int l,const int r,const int pos) { if (l==r)return cur; int mid=(l+r)>>1; if (pos<=mid)return query(t[cur].lc,l,mid,pos); else return query(t[cur].rc,mid+1,r,pos); } inline void work() { int n=read(),m=read(); for (int i=1,a,b;i<=m;i++) a=read(),b=read(), e[i<<1].too=b,e[i<<1].nxt=last[a],last[a]=i<<1, e[i<<1|1].too=a,e[i<<1|1].nxt=last[b],last[b]=i<<1|1, store[i].a=a,store[i].b=b, store[i].len=e[i<<1].len=e[i<<1|1].len=read(), store[i].h=e[i<<1].h=e[i<<1|1].h=read(); dij(); sort(store+1,store+1+m,cmp); int cnt=1;h[1]=store[1].h;h[0]=2e9;rt[1]=0; for (int i=1;i<=n;i++) { if (i==store[1].a) update(rt[1],1,n,i,i,min(dist[i],dist[store[1].b]),2,1); else if (i==store[1].b) update(rt[1],1,n,i,store[1].a,dist[i],1,1); else update(rt[1],1,n,i,i,dist[i],1,1); } for (int i=2;i<=m;i++) { if (store[i].h!=store[i-1].h)h[++cnt]=store[i].h,rt[cnt]=rt[cnt-1]; int a=query(rt[cnt],1,n,store[i].a),b=query(rt[cnt],1,n,store[i].b),tmpa=store[i].a,tmpb=store[i].b; while (t[a].val!=tmpa)tmpa=t[a].val,a=query(rt[cnt],1,n,t[a].val); while (t[b].val!=tmpb)tmpb=t[b].val,b=query(rt[cnt],1,n,t[b].val); if (t[a].val!=t[b].val) { if (t[a].siz<t[b].siz)swap(a,b); update(rt[cnt],1,n,t[a].val,t[a].val,min(t[a].mn,t[b].mn),t[a].siz+t[b].siz,cnt); update(rt[cnt],1,n,t[b].val,t[a].val,t[b].mn,t[b].siz,cnt); } } int q=read(),K=read(),S=read(); ll lastans=0; while (q--) { int v=(read()+K*lastans-1)%n+1,p=(read()+K*lastans)%(S+1); int l=0,r=cnt,mid; while (l<r) { mid=((l+r)>>1)+1; if (p<h[mid])l=mid;else r=mid-1; } if (l==0)printf("%lld\n",lastans=dist[v]); else if (l==cnt&&p<h[cnt])lastans=0,puts("0"); else { int tmp; while (t[tmp=query(rt[l],1,n,v)].val!=v)v=t[query(rt[l],1,n,t[tmp].val)].val; printf("%lld\n",lastans=t[tmp].mn); } } } signed main() { freopen("return.in","r",stdin); freopen("return.out","w",stdout); T=read(); for (tt=1;tt<=T;tt++)work(),clear(); } |
- 关于SPFA：“它已经死了”
Subscribe
0 评论