[文章目录]
Description
n个点，m条边的无向图，每条边有A,B两个参数，找一条路径使得路径上的边的A的最大值与B的最大值的和最小。
考虑只有A的话，直接就是最小生成树上的路径。
那么两个权值的话，我们按照kruskal的思路，按照A从小到大加边，LCT维护动态关于B的最小生成树。用当前A的权值和最小生成树上两个点的链上的边的最大值的和更新答案即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
int n,m;
struct edge
{
int x,y,a,b;
}e[101000];
bool cmp(edge x,edge y){return x.a<y.a;}
struct Splay
{
Splay *c[2],*fa;
int w,mx;
bool tur;
Splay(int x);
void reverse(){swap(c[0],c[1]),tur^=1;}
void pushup(){mx=max(c[0]->mx,max(c[1]->mx,w));}
void pushdown();
}*null=new Splay(0),*t[51000];
Splay::Splay(int x)
{
c[0]=c[1]=fa=null ? null : this;
w=mx=x; tur=false;
}
void Splay::pushdown()
{
if(tur)
{
if(c[0]!=null) c[0]->reverse();
if(c[1]!=null) c[1]->reverse();
tur=0;
}
}
bool isr(Splay *x){return x!=x->fa->c[0]&&x!=x->fa->c[1];}
void turall(Splay *x)
{
if(!isr(x)) turall(x->fa);
x->pushdown();
}
void rotate(Splay *x)
{
if(isr(x)) return ;
Splay *y=x->fa; int l=(x==y->c[1]),r=l^1;
y->c[l]=x->c[r]; x->c[r]->fa=y;
x->c[r]=y; x->fa=y->fa;
if(!isr(y)) y->fa->c[y==y->fa->c[1]]=x;
y->fa=x; y->pushup(); x->pushup();
}
void splay(Splay *x)
{
turall(x);
while(!isr(x))
{
Splay *y=x->fa;
if(!isr(y)) rotate((x==y->c[0])^(y==y->fa->c[0])?x:y);
rotate(x);
}
}
void access(Splay *x)
{
Splay *t=null;
while(x!=null)
{
splay(x);
x->c[1]=t; t=x;
x->pushup(); x=x->fa;
}
}
void moveroot(Splay *x) {access(x); splay(x); x->reverse();}
void link(Splay *x,Splay *y) {moveroot(x); x->fa=y;}
void cut(Splay *x,Splay *y)
{
moveroot(x); access(y); splay(y);
x->fa=y->c[0]=null; y->pushup();
}
bool atsame(Splay *x,Splay *y)
{
while(x->fa!=null) x=x->fa;
while(y->fa!=null) y=y->fa;
return x==y;
}
Splay *find_mx(Splay *x)
{
if(x->w>=x->c[0]->mx&&x->w>=x->c[1]->mx) return splay(x),x;
if(x->c[0]->mx>x->c[1]->mx) return find_mx(x->c[0]);
else return find_mx(x->c[1]);
}
int main()
{
scanf("%d%d",&n,&m);
int i,ans=inf;
for(i=1;i<=m;++i) scanf("%d%d%d%d",&e[i].x,&e[i].y,&e[i].a,&e[i].b);
for(i=1;i<=n;++i) t[i]=new Splay(0);
sort(e+1,e+m+1,cmp);
Splay *p;
for(i=1;i<=m;++i)
{
if(!atsame(t[e[i].x],t[e[i].y]))
{
p=new Splay(e[i].b);
link(t[e[i].x],p);
link(t[e[i].y],p);
}
else
{
moveroot(t[e[i].x]);
access(t[e[i].y]);
splay(t[e[i].y]);
if(t[e[i].y]->mx>e[i].b)
{
splay(p=find_mx(t[e[i].y]));
p->pushdown();
if(p->c[0]!=null) p->c[0]->fa=null;
if(p->c[1]!=null) p->c[1]->fa=null;
free(p); p=new Splay(e[i].b);
link(t[e[i].x],p);
link(t[e[i].y],p);
}
}
if(atsame(t[1],t[n]))
{
moveroot(t[1]);
access(t[n]);
splay(t[n]);
ans=min(ans,t[n]->mx+e[i].a);
}
}
if(ans==inf) puts("-1");
else printf("%d\n",ans);
return 0;
}