[ zerojudge ] b483:史蒂芙的觀察日記 (link cut tree)

題目:
http://zerojudge.tw/ShowProblem?problemid=b483

解法:
動態加邊的最小生成森林
每增加一條邊後，如果產生環，可以利用迴路性質將環上的最大邊刪除，這個操作可以用link cut tree完成，因為link cut tree無法維護邊權，所以我們把邊轉化成點，也就是在兩個點之間的邊改成一個點，分別連到這兩個點，而他的權重就是邊的權重，類似於這樣:
u-v -> u-k-v，k存的是uv邊的邊權
如此一來只要想辦法維護好原來的那些點權讓他們不會影響到邊權即可

code:

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 125

#include<bits/stdc++.h> #define MAXN 200005 using namespace std; struct edge{ int s,t,w; }e[MAXN/2]; struct splay_tree{ int pa,ch[2]; bool rev; int ma; splay_tree():pa(0),rev(0),ma(0){ch[0]=ch[1]=0;} }node[MAXN]; int v[MAXN]; int n,m; inline bool isroot(int x){ return node[node[x].pa].ch[0]!=x&&node[node[x].pa].ch[1]!=x; } inline void up(int x){ int lc=node[x].ch[0],rc=node[x].ch[1]; node[x].ma=(v[node[lc].ma]>v[node[rc].ma])?node[lc].ma:node[rc].ma; node[x].ma=v[x]>v[node[x].ma]?x:node[x].ma; } inline void down(int x){ if(node[x].rev){ if(node[x].ch[0])node[node[x].ch[0]].rev^=1; if(node[x].ch[1])node[node[x].ch[1]].rev^=1; std::swap(node[x].ch[0],node[x].ch[1]); node[x].rev^=1; } } void push_down(int x){ if(!isroot(x))push_down(node[x].pa); down(x); } inline void rotate(int x){ int y=node[x].pa,z=node[y].pa,d=(node[y].ch[1]==x); node[x].pa=z; if(!isroot(y))node[z].ch[node[z].ch[1]==y]=x; node[y].ch[d]=node[x].ch[d^1]; node[node[y].ch[d]].pa=y; node[y].pa=x,node[x].ch[d^1]=y; up(y); up(x); } inline void splay(int x){ push_down(x); while(!isroot(x)){ int y=node[x].pa; if(!isroot(y)){ int z=node[y].pa; if((node[z].ch[0]==y)^(node[y].ch[0]==x))rotate(y); else rotate(x); } rotate(x); } } inline int access(int x){ int last=0; while(x){ splay(x); node[x].ch[1]=last; up(x); last=x; x=node[x].pa; } return last; } inline void make_root(int x){ access(x),splay(x); node[x].rev^=1; } inline void add(int x){ int s=e[x].s,t=e[x].t; make_root(t),node[t].pa=x+n; node[x+n].pa=s; v[x+n]=e[x].w; node[x+n].ma=x+n; } inline void del(int x){ int u=e[x].s,v=e[x].t; make_root(u); access(v),splay(v); node[v].ch[0]=0; node[v].ma=node[u].ma=0; node[u].pa=node[x+n].pa=0; node[u].ch[1]=0; } inline int find_root(int x){ x=access(x); while(node[x].ch[0])x=node[x].ch[0]; splay(x); return x; } int ans; inline void insert(int x){ int u=e[x].s,v=e[x].t,w=e[x].w; if(find_root(u)!=find_root(v))add(x),ans+=w; else{ make_root(u),access(v),splay(v); if(e[node[v].ma-n].w>w){ ans-=e[node[v].ma-n].w; del(node[v].ma-n); ans+=w; add(x); } } } int main(){ for(int cnt=1;~scanf("%d%d",&n,&m);++cnt){ printf("Case #%d\n",cnt); for(int i=0;i<n+m+1;++i){ node[i].ch[0]=node[i].ch[1]=0; node[i].ma=node[i].pa=0; node[i].rev=0; v[i]=0; } ans=0; for(int i=1;i<=m;++i){ scanf("%d%d%d",&e[i].s,&e[i].t,&e[i].w); insert(i); printf("%d\n",ans); } } return 0; }