bzoj3669: [Noi2014]魔法森林【lct】【最小生成树】

Description

为了得到书法大家的真传，小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型守护精灵的个数之和。

Input

第1行包含两个整数N,M，表示无向图共有N个节点，M条边。接下来M行，第行包含4个正整数Xi,Yi,Ai,Bi，描述第i条无向边。其中Xi与Yi为该边两个端点的标号，Ai与Bi的含义如题所述。注意数据中可能包含重边与自环。

Output

输出一行一个整数：如果小E可以成功拜访到隐士，输出小E最少需要携带的守护精灵的总个数；如果无论如何小E都无法拜访到隐士，输出“-1”（不含引号）。

Sample Input

【输入样例1】
4 5
1 2 19 1
2 3 8 12
2 4 12 15
1 3 17 8
3 4 1 17

【输入样例2】
3 1
1 2 1 1

Sample Output

【输出样例1】

32
【样例说明1】
如果小E走路径1→2→4，需要携带19+15=34个守护精灵；
如果小E走路径1→3→4，需要携带17+17=34个守护精灵；
如果小E走路径1→2→3→4，需要携带19+17=36个守护精灵；
如果小E走路径1→3→2→4，需要携带17+15=32个守护精灵。
综上所述，小E最少需要携带32个守护精灵。

【输出样例2】

-1
【样例说明2】
小E无法从1号节点到达3号节点，故输出-1。

HINT

2<=n<=50,000

0<=m<=100,000
1<=ai ,bi<=50,000

最近在学lct……终于是会一点点了……吧……

看到题秒想到最小生成树，但是感觉直接加边根本确保不了题目要求……于是没有往下想QAQ

然后想了很久乱七八糟的东西……最后！哦排序a就可以了啊！摔！

感觉是对的……于是翻了题解……的确是这样w

【今天被一名强者D了一发问我怎么证明，然后发现只能稍微口胡一下QAQ】

【考虑每一次加边，都会形成一种状态，此时若1与n联通，那么根据维护的最小生成树最大的b值一定在当前最小，而a值是递增的，那么此时的a值就是最大的a值。此时将相加的值与res比较，min（res，a+b）即可……大概吧……】

具体维护的话，根据最小生成树的性质，当加入此边可以构成一个环时，去掉最长的边就是最小生成树了，所以就只有维护一个max值。

但是在这里，边权并不能直接转换为点权，所以就可以把边看成在两点间的某一点，即：

将u，v相连转化为link（u，edge），link（v,edge）

然后直接维护lct……

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstdlib>
  4 #include<cstring>
  5 #include<string>
  6 #include<cmath>
  7 #include<algorithm>
  8 #include<queue>
  9 #include<vector>
 10 using namespace std;
 11 #define maxn 400005
 12 #define Max 1e9
 13 int read()
 14 {
 15     int f=1,p=0;
 16     char c=getchar();
 17     while (c<'0'||c>'9'){if (c=='-')f=-1;c=getchar();}
 18     while (c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}
 19     return f*p;
 20 }
 21 int n,m,res=Max;
 22 int mn[maxn],p[maxn],re[maxn],fa[maxn],ch[maxn][2],mx[maxn],val[maxn],st[maxn];
 23 struct edge
 24 {
 25     int u,v,a,b;
 26 }e[maxn];
 27 int cmp(edge x,edge y)
 28 {
 29     //if (x.a==y.a) return x.b<y.b;
 30     return x.a<y.a;
 31 }
 32 int isroot(int x){return !fa[x]||(ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x);}
 33 void upd(int x)
 34 {
 35     mx[x]=x;
 36     if (val[mx[x]]<val[mx[ch[x][0]]]) mx[x]=mx[ch[x][0]];
 37     if (val[mx[x]]<val[mx[ch[x][1]]]) mx[x]=mx[ch[x][1]];
 38 }
 39 void rot(int x)
 40 {
 41     int y=fa[x],z=fa[y],f=(ch[y][1]==x);
 42     ch[y][f]=ch[x][f^1];ch[x][f^1]=y;
 43     if (ch[y][f]) fa[ch[y][f]]=y;
 44     if (!isroot(y)) ch[z][ch[z][1]==y]=x;
 45     fa[y]=x;fa[x]=z;upd(y);upd(x);
 46 }
 47 void makedown(int x)
 48 {
 49     if (!x) return ;
 50     if (re[x])
 51     {
 52         re[x]=0;
 53         swap(ch[x][0],ch[x][1]);
 54         if (ch[x][0]) re[ch[x][0]]^=1;
 55         if (ch[x][1]) re[ch[x][1]]^=1;
 56     }
 57 }
 58 void splay(int x)
 59 {
 60     if (!x) return ;
 61     makedown(fa[x]);makedown(x);
 62     while (!isroot(x))
 63     {
 64         makedown(fa[fa[x]]);makedown(fa[x]);makedown(x);
 65         if (isroot(fa[x])) rot(x);
 66         else if ((ch[fa[x]][1]==x)==(ch[fa[fa[x]]][1]==fa[x])) rot(fa[x]),rot(x);
 67         else rot(x),rot(x);
 68     }
 69     upd(x);
 70 }
 71 void access(int x)
 72 {
 73     int y=0;
 74     while (x)
 75     {
 76         splay(x);
 77         ch[x][1]=y;
 78         upd(x);
 79         y=x;
 80         x=fa[x];
 81     }
 82 }
 83 void makeroot(int x)
 84 {access(x);splay(x);re[x]^=1;}
 85 void link(int u,int v)
 86 {makeroot(u);fa[u]=v;}
 87 void cut(int u,int v)
 88 {makeroot(u);access(v);splay(v);ch[v][0]=0;fa[u]=0;upd(v);}
 89 int query(int u,int v)
 90 {makeroot(u);access(v);splay(v);return mx[v];}
 91 int getf(int x)
 92 {return x==p[x]?x:p[x]=getf(p[x]);}
 93 void merge(int x,int y)
 94 {
 95     int t1=getf(x),t2=getf(y);
 96     if (t1!=t2)
 97     {
 98         p[t1]=t2;
 99     }
100 }
101 int main()
102 {
103     freopen("in.txt","r",stdin);
104     n=read();m=read();
105     for (int i=1;i<=m;i++)
106     {
107         int u=read(),v=read(),a=read(),b=read();
108         e[i].u=u;e[i].v=v;e[i].a=a;e[i].b=b;
109     }
110     sort(e+1,e+m+1,cmp);
111     for (int i=1;i<=n;i++) p[i]=i;
112     for (int i=1;i<=m;i++)
113     {
114         int u=e[i].u,v=e[i].v,a=e[i].a,b=e[i].b;
115         if (getf(u)==getf(v))
116         {
117            int t=query(u,v);
118            if (val[t]>b)
119            {
120                cut(e[t-n].u,t);
121                cut(e[t-n].v,t);
122            }
123            else
124            {if (getf(1)==getf(n)) res=min(res,a+val[query(1,n)]);continue;}
125         }
126         else
127         {
128             merge(u,v);
129         }
130         mx[i+n]=i+n;val[i+n]=b;
131         link(u,i+n);link(v,i+n);
132         if (getf(1)==getf(n)) {res=min(res,e[i].a+val[query(1,n)]);}
133     }
134     if (res==Max) puts("-1");
135     else printf("%d",res);
136     return 0;
137 }

我好弱啊天天被d