2959: 長跑

Description

　　某校開展了同學們喜聞樂見的陽光長跑活動。為了能“為祖國健康工作五十年”，同學們紛紛離開寢室，離開教室，離開實驗室，到操場參加3000米長跑運動。一時間操場上熙熙攘攘，摩肩接踵，盛況空前。
　　為了讓同學們更好地監督自己，學校推行了刷卡機制。
　　學校中有n個地點，用1到n的整數表示，每個地點設有若干個刷卡機。
　　有以下三類事件：
　　1、修建了一條連接A地點和B地點的跑道。
　　2、A點的刷卡機臺數變為了B。
　　3、進行了一次長跑。問一個同學從A出發，最后到達B最多可以刷卡多少次。具體的要求如下：
　　當同學到達一個地點時，他可以在這里的每一臺刷卡機上都刷卡。但每臺刷卡機只能刷卡一次，即使多次到達同一地點也不能多次刷卡。
　　為了安全起見，每條跑道都需要設定一個方向，這條跑道只能按照這個方向單向通行。最多的刷卡次數即為在任意設定跑道方向，按照任意路徑從A地點到B地點能刷卡的最多次數。

Input

　　輸入的第一行包含兩個正整數n,m，表示地點的個數和操作的個數。
　　第二行包含n個非負整數，其中第i個數為第個地點最開始刷卡機的臺數。
　　接下來有m行，每行包含三個非負整數P,A,B，P為事件類型，A,B為事件的兩個參數。
　　最初所有地點之間都沒有跑道。
　　每行相鄰的兩個數之間均用一個空格隔開。表示地點編號的數均在1到n之間，每個地點的刷卡機臺數始終不超過10000，P=1,2,3。

Output

　　輸出的行數等于第3類事件的個數，每行表示一個第3類事件。如果該情況下存在一種設定跑道方向的方案和路徑的方案，可以到達，則輸出最多可以刷卡的次數。如果A不能到達B，則輸出-1。

---

思路：用LCT維護鏈的信息，用并查集進行縮點。

注意到每次縮點后只有虛邊連的邊是不對的，所以在access時重新練一下虛邊和詢問的時候詢問并查集的根就可以了，但是bzoj我還是沒卡過去...

---

Code:

#include <cstdio> #include <cctype> #define ll long long #define fa par[now] #define ls ch[now][0] #define rs ch[now][1] const int N=150010; int read() {int x=0;char c=getchar();while(!isdigit(c)) c=getchar();while(isdigit(c)) {x=x*10+c-'0';c=getchar();}return x; } int ch[N][2],par[N],tag[N],s[N],F[N],tot,tmp,n,m; ll sum[N],dat[N],Dat[N]; int Find(int x){return F[x]=F[x]==x?x:Find(F[x]);} int identity(int now){return ch[fa][1]==now;} bool isroot(int now){return ch[fa][0]==now||ch[fa][1]==now;} void updata(int now){sum[now]=sum[ls]+sum[rs]+dat[now];} void Reverse(int now){tag[now]^=1,tmp=ls,ls=rs,rs=tmp;} void connect(int f,int now,int typ){ch[fa=f][typ]=now;} void pushdown(int now) {if(tag[now]){if(ls) Reverse(ls);if(rs) Reverse(rs);tag[now]^=1;} } void Rotate(int now) {int p=Find(fa),typ=identity(now);connect(p,ch[now][typ^1],typ);if(isroot(p)) connect(par[p],now,identity(p));else fa=Find(par[p]);connect(now,p,typ^1);updata(p),updata(now); } void splay(int now) {while(isroot(now)) s[++tot]=now,now=fa;s[++tot]=now;while(tot) pushdown(s[tot--]);now=s[1];for(;isroot(now);Rotate(now))if(isroot(fa))Rotate(identity(now)^identity(fa)?now:fa); } void access(int now) {for(int las=0;now;las=now,now=(fa=Find(fa)))splay(now),rs=las,updata(now); } void evert(int now){access(now),splay(now),Reverse(now);} int findroot(int now) {access(now);splay(now);while(ls) now=ls;return now; } void dfs(int now,int anc) {if(!now) return;F[now]=anc;dfs(ls,anc),dfs(rs,anc); } void link(int u,int v) {evert(u);if(findroot(v)!=u) par[u]=v;else dat[v]=sum[v],dfs(v,v),ch[v][0]=ch[v][1]=0; } void query(int u,int v) {evert(u);if(findroot(v)!=u) puts("-1");else printf("%lld\n",sum[v]); } int main() {freopen("data.in","r",stdin);freopen("dew.out","w",stdout);n=read(),m=read();for(int i=1;i<=n;i++) F[i]=i,Dat[i]=sum[i]=dat[i]=read();for(int op,x,y,i=1;i<=m;i++){op=read(),x=read(),y=read();if(op==1)link(Find(x),Find(y));else if(op==2){int rt=Find(x);splay(rt);dat[rt]+=y-Dat[x];Dat[x]=y;updata(rt);}elsequery(Find(x),Find(y));}return 0; }

---

2018.12.11

轉載于:https://www.cnblogs.com/butterflydew/p/10104352.html

總結

以上是生活随笔為你收集整理的BZOJ 2959: 长跑 解题报告的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。