为了得到书法大家的真传，小E同学下定决心去拜访住在魔法森林中的隐士。魔法森林可以被看成一个包含个N节点M条边的无向图，节点标号为1..N，边标号为1..M。初始时小E同学在号节点1，隐士则住在号节点N。小E需要通过这一片魔法森林，才能够拜访到隐士。
魔法森林中居住了一些妖怪。每当有人经过一条边的时候，这条边上的妖怪就会对其发起攻击。幸运的是，在号节点住着两种守护精灵：A型守护精灵与B型守护精灵。小E可以借助它们的力量，达到自己的目的。
只要小E带上足够多的守护精灵，妖怪们就不会发起攻击了。具体来说，无向图中的每一条边Ei包含两个权值Ai与Bi。若身上携带的A型守护精灵个数不少于Ai，且B型守护精灵个数不少于Bi，这条边上的妖怪就不会对通过这条边的人发起攻击。当且仅当通过这片魔法森林的过程中没有任意一条边的妖怪向小E发起攻击，他才能成功找到隐士。
由于携带守护精灵是一件非常麻烦的事，小E想要知道，要能够成功拜访到隐士，最少需要携带守护精灵的总个数。守护精灵的总个数为A型守护精灵的个数与B型守护精灵的个数之和。
第1行包含两个整数N,M，表示无向图共有N个节点，M条边。 接下来M行，第行包含4个正整数Xi,Yi,Ai,Bi，描述第i条无向边。其中Xi与Yi为该边两个端点的标号，Ai与Bi的含义如题所述。 注意数据中可能包含重边与自环。
输出一行一个整数：如果小E可以成功拜访到隐士，输出小E最少需要携带的守护精灵的总个数；如果无论如何小E都无法拜访到隐士，输出“-1”（不含引号）。
1 #include <iostream> 2 #include <algorithm> 3 #include <cstring> 4 #include <cstdio> 5 using namespace std; 6 const int maxn=200010; 7 const int maxm=200010; 8 9 int A[maxm],B[maxm],U[maxm],V[maxm],P[maxm]; 10 int fa[maxn+maxm],ch[maxn+maxm][2],Max[maxm+maxn],Mpos[maxn+maxm],key[maxn+maxm],flip[maxn+maxm]; 11 int f[maxn]; 12 bool rt[maxn+maxm]; 13 14 void Flip(int p){ 15 if(!p)return; 16 swap(ch[p][0],ch[p][1]); 17 flip[p]^=1; 18 } 19 20 void Push_down(int p){ 21 if(flip[p]){ 22 Flip(ch[p][0]); 23 Flip(ch[p][1]); 24 flip[p]=0; 25 } 26 } 27 28 void Push_up(int p){ 29 Max[p]=max(key[p],max(Max[ch[p][0]],Max[ch[p][1]])); 30 if(Max[p]==key[p]) 31 Mpos[p]=p; 32 else if(Max[p]==Max[ch[p][0]]) 33 Mpos[p]=Mpos[ch[p][0]]; 34 else if(Max[p]==Max[ch[p][1]]) 35 Mpos[p]=Mpos[ch[p][1]]; 36 } 37 38 void Pd(int p){ 39 if(!rt[p])Pd(fa[p]); 40 Push_down(p); 41 } 42 43 void Rotate(int x){ 44 int y=fa[x],g=fa[y],c=ch[y][1]==x; 45 ch[y][c]=ch[x][c^1]; 46 ch[x][c^1]=y; 47 fa[y]=x;fa[ch[y][c]]=y; 48 fa[x]=g; 49 if(rt[y]) 50 rt[y]=false,rt[x]=true; 51 else 52 ch[g][ch[g][1]==y]=x; 53 Push_up(y); 54 } 55 56 void Splay(int x){ 57 Pd(x); 58 for(int y=fa[x];!rt[x];Rotate(x),y=fa[x]) 59 if(!rt[y]) 60 Rotate((ch[fa[y]][1]==y)==(ch[y][1]==x)?y:x); 61 Push_up(x); 62 } 63 64 void Access(int x){ 65 int y=0; 66 while(x){ 67 68 Splay(x); 69 70 rt[ch[x][1]]=true; 71 rt[ch[x][1]=y]=false; 72 Push_up(x); 73 x=fa[y=x]; 74 } 75 } 76 77 void Make_root(int x){ 78 Access(x); 79 Splay(x); 80 Flip(x); 81 } 82 83 void Link(int x,int y){ 84 Make_root(x); 85 fa[x]=y; 86 } 87 void Cut(int x,int y){ 88 Make_root(x); 89 Splay(y); 90 fa[ch[y][0]]=fa[y]; 91 rt[ch[y][0]]=true; 92 fa[y]=0;ch[y][0]=0; 93 Push_up(y); 94 } 95 96 void Lca(int &x,int &y){ 97 Access(y);y=0; 98 while(true){ 99 Splay(x); 100 if(!fa[x])return; 101 rt[ch[x][1]]=true; 102 rt[ch[x][1]=y]=false; 103 Push_up(x); 104 x=fa[y=x]; 105 } 106 } 107 108 int Query(int x,int y){ 109 Lca(x,y); 110 int ret=max(key[x],max(Max[ch[x][1]],Max[y])); 111 if(ret==key[x]) 112 return x; 113 else if(ret==Max[ch[x][1]]) 114 return Mpos[ch[x][1]]; 115 return Mpos[y]; 116 } 117 118 int find(int x){ 119 return f[x]==x?x:f[x]=find(f[x]); 120 } 121 122 bool cmp(int a,int b){ 123 return A[a]<A[b]; 124 } 125 126 int main(){ 127 int n,m,S,T,ans; 128 scanf("%d%d",&n,&m); 129 for(int i=1;i<=m;P[i]=i,i++) 130 scanf("%d%d%d%d",&U[i],&V[i],&A[i],&B[i]); 131 for(int i=1;i<=n+m;i++)rt[i]=true; 132 for(int i=1;i<=n;i++)f[i]=i; 133 sort(P+1,P+m+1,cmp); 134 S=1,T=n; 135 ans=2147483647; 136 for(int i=1;i<=m;i++){ 137 Max[n+P[i]]=key[n+P[i]]=B[P[i]]; 138 139 if(find(U[P[i]])!=find(V[P[i]])){ 140 Link(U[P[i]],n+P[i]); 141 Link(V[P[i]],n+P[i]); 142 f[find(U[P[i]])]=find(V[P[i]]); 143 } 144 else{ 145 int p=Query(U[P[i]],V[P[i]]); 146 if(B[p-n]>B[P[i]]){ 147 Cut(U[p-n],p); 148 Cut(V[p-n],p); 149 Link(U[P[i]],P[i]+n); 150 Link(V[P[i]],P[i]+n); 151 } 152 else 153 continue; 154 } 155 if(find(S)==find(T)) 156 ans=min(ans,A[P[i]]+B[Query(S,T)-n]); 157 } 158 printf("%d\n",(ans==2147483647)?-1:ans); 159 }
原文：http://www.cnblogs.com/TenderRun/p/5284088.html