这题似乎不好直接做,可以考虑按照(a_i)升序排序,然后依次加边更新答案
具体实现方法是用lct维护当前的树,这里需要维护链上最大的(b_i).每次加一条边,如果加完以后没有环直接加,否则找出链上最大的(b_i),如果这个(b_i)比当前的(b_i)小,加了肯定不优,否则就把那条边断掉,加上这条边.每次用当前(a_i)和1到n链上最大(b_i)更新答案
#include<bits/stdc++.h>
#define LL long long
#define db long double
#define il inline
using namespace std;
const int N=1e5+10;
il LL rd()
{
LL x=0,w=1;char ch=0;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
int n,m,w[N],po[N][2],tt;
int fa[N],ch[N][2],id[N],vi[N];
bool tg[N];
bool nrt(int x){return ch[fa[x]][0]==x||ch[fa[x]][1]==x;}
void psup(int x)
{
id[x]=w[id[ch[x][0]]]>w[id[ch[x][1]]]?id[ch[x][0]]:id[ch[x][1]];
id[x]=w[id[x]]>w[vi[x]]?id[x]:vi[x];
}
void rev(int x){if(x) swap(ch[x][0],ch[x][1]),tg[x]^=1;}
void psdn(int x){if(tg[x]) rev(ch[x][0]),rev(ch[x][1]),tg[x]=0;}
void ppush(int x)
{
if(nrt(x)) ppush(fa[x]);
psdn(x);
}
void rot(int x)
{
int y=fa[x],z=fa[y],yy=ch[y][1]==x,w=ch[x][!yy];
if(nrt(y)) ch[z][ch[z][1]==y]=x;
ch[y][yy]=w,ch[x][!yy]=y;
if(w) fa[w]=y;
fa[x]=z,fa[y]=x;
psup(y);
}
void spl(int x)
{
ppush(x);
while(nrt(x))
{
int y=fa[x];
if(nrt(y)) ((ch[y][1]==x)^(ch[fa[y]][1]==y))?rot(x):rot(y);
rot(x);
}
psup(x);
}
void acs(int x)
{
for(int y=0;x;y=x,x=fa[x])
spl(x),ch[x][1]=y,psup(x);
}
void mkrt(int x)
{
acs(x),spl(x),rev(x);
}
int fdrt(int x)
{
acs(x),spl(x);
psdn(x);
while(ch[x][0]) x=ch[x][0],psdn(x);
return x;
}
void split(int x,int y)
{
mkrt(x),acs(y),spl(y);
}
void link(int x,int y,int z)
{
mkrt(x);
if(fdrt(y)!=x)
{
mkrt(y);
w[++tt]=z,vi[tt]=tt,po[tt][0]=x,po[tt][1]=y;
fa[x]=fa[y]=tt;
return;
}
acs(y),spl(y);
int ii=id[y];
if(w[ii]<=z) return;
mkrt(po[ii][0]),acs(po[ii][1]),spl(ii);
fa[po[ii][0]]=fa[po[ii][1]]=ch[ii][0]=ch[ii][1]=0,psup(ii);
w[ii]=z,po[ii][0]=x,po[ii][1]=y;
mkrt(x),mkrt(y);
fa[x]=fa[y]=ii;
}
struct edge
{
int x,y,a,b;
bool operator < (const edge &bb) const {return a<bb.a;}
}e[N];
int main()
{
n=rd(),m=rd();
for(int i=1;i<=m;++i)
{
int x=rd(),y=rd(),a=rd(),b=rd();
e[i]=(edge){x,y,a,b};
}
sort(e+1,e+m+1);
tt=n,w[0]=-(1<<30);
int ans=1<<30;
for(int i=1;i<=m;++i)
{
if(e[i].x==e[i].y) continue;
link(e[i].x,e[i].y,e[i].b);
mkrt(1);
if(fdrt(n)==1) ans=min(ans,e[i].a+w[id[n]]);
}
printf("%d
",ans<(1<<29)?ans:-1);
return 0;
}