【BZOJ3669】[Noi2014]魔法森林 LCT

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #define N 50050
  5 #define M 100100
  6 #define inf 0x7fffffff
  7 using namespace std;
  8 int n,m,ans; 
  9 struct E{int x,y,a,b;}e[M];
 10 struct node
 11 {
 12     node *fa,*ch[2];
 13     void init();
 14     int pos,rpos;
 15     bool rev;
 16     bool chr() {return this==fa->ch[1];}
 17     bool isrt() {return this!=fa->ch[1] && this!=fa->ch[0];}
 18     void setc(node *x,int t) {this->ch[t]=x; x->fa=this;}
 19     void push_up();
 20     void push_down();
 21 /*    void push_down()
 22     {
 23         if (this==null) return;
 24         if (!x->isrt()) x->fa->push_down();
 25         if (rev)
 26         {
 27             ch[1]->rev^=1;
 28             ch[0]->rev^=1;
 29             swap(ch[1],ch[0]);
 30             rev=0;
 31         }
 32     }
 33     void push_up()
 34     {
 35         if (this==null) return;
 36         pos=rpos;
 37         if (ch[0]!=null && e[pos].b<e[ch[0]->pos].b)    pos=ch[0]->pos;
 38         if (ch[1]!=null && e[pos].b<e[ch[1]->pos].b)    pos=ch[1]->pos;
 39     }*/
 40 }pool[N+M],*pt=pool,*point[N],*et[M],*null;
 41 void node::init() {ch[0]=ch[1]=fa=null; pos=0; rev=0; rpos=0;}
 42 void node::push_up()
 43 {
 44     if (this==null) return;
 45     pos=rpos;
 46     if (ch[0]!=null && e[pos].b<e[ch[0]->pos].b)    pos=ch[0]->pos;
 47     if (ch[1]!=null && e[pos].b<e[ch[1]->pos].b)    pos=ch[1]->pos;
 48 } 
 49 void node::push_down()
 50 {
 51     if (this==null) return;
 52         if (!this->isrt()) this->fa->push_down();
 53         if (rev)
 54         {
 55             if (ch[1]!=null) ch[1]->rev^=1;
 56             if (ch[0]!=null) ch[0]->rev^=1;
 57             swap(ch[1],ch[0]);
 58             rev=0;
 59         }
 60 }
 61 namespace LCT
 62 {
 63     node *NewNode()
 64     {
 65         pt++;
 66         pt->init();
 67         return pt;
 68     }
 69     void rotate(node *x)
 70     {
 71         node *r=x->fa;
 72         if (x==null || r==null) return;
 73         int t=x->chr();
 74         if (r->isrt()) x->fa=r->fa;
 75         else r->fa->setc(x,r->chr());
 76         r->setc(x->ch[t^1],t);
 77         x->setc(r,!t);
 78         x->push_up(); r->push_up();
 79     }
 80     void Splay(node *x)
 81     {
 82         x->push_down();
 83         for (;!x->isrt();rotate(x))
 84             if (!x->fa->isrt())
 85                 if (x->chr()==x->fa->chr()) rotate(x->fa);
 86                 else rotate(x);
 87         x->push_up();
 88     }
 89     void Access(node *x)
 90     {
 91         node *r=null;
 92         for (;x!=null;r=x,x=x->fa)
 93         {
 94             Splay(x);
 95             x->ch[1]=r;
 96         }
 97     }
 98     void MoveRoot(node *x)
 99     {
100         Access(x);
101         Splay(x);
102         x->rev^=1;
103     }
104     void Link(node *x,node *y)
105     {
106         MoveRoot(x);
107         x->fa=y;
108     }
109     void Cut(node *x,node *y)
110     {
111         MoveRoot(x);
112         Access(y); Splay(y);
113         y->ch[0]->fa=null; y->ch[0]=null;
114     }
115     node *Find(node *x)
116     {
117         Access(x);
118         Splay(x);
119         while (x->ch[0]!=null) x=x->ch[0];
120         return x;
121     }
122     int Query(node *x,node *y)
123     {
124         MoveRoot(x);
125         Access(y);Splay(y);
126         return y->pos;
127     }
128 }
129 inline int read()
130 {
131     char c;
132     int ans=0,f=1;
133     while (!isdigit(c=getchar())) if (c==‘-‘) f=-1;
134     ans=c-‘0‘;
135     while (isdigit(c=getchar())) ans=ans*10+c-‘0‘;
136     return ans*f;
137 }
138 inline bool cmp (E a,E b) {return a.a<b.a;}
139 using namespace LCT;
140 int main()
141 {
142     n=read();m=read();
143     null=pt++;
144     null->init();
145     for (int i=1;i<=m;i++) {e[i].x=read(); e[i].y=read(); e[i].a=read(); e[i].b=read();}
146     for (int i=1;i<=n;i++)     point[i]=NewNode();
147     sort(e+1,e+m+1,cmp);
148     ans=inf;e[0].b=-inf;
149     for (int i=1;i<=m;i++)
150     {
151         int x=e[i].x,y=e[i].y,b=e[i].b;
152         et[i]=NewNode(); et[i]->pos=et[i]->rpos=i;
153         if (Find(point[x])==Find(point[y]))
154         {
155             int pos=Query(point[x],point[y]);
156             if (e[pos].b>b)
157             {
158                 Cut(et[pos],point[e[pos].x]);
159                 Cut(et[pos],point[e[pos].y]);
160                 Link(et[i],point[x]);
161                 Link(et[i],point[y]);
162             }
163         }
164         else 
165         {
166             Link(et[i],point[x]);
167             Link(et[i],point[y]);
168         }
169         if (Find(point[1])==Find(point[n])) ans=min(ans,e[i].a+e[Query(point[1],point[n])].b);
170     }
171     if (ans!=inf) printf("%d\n",ans);
172     else printf("-1\n");
173     return 0; 
174 }