点击这里查看原题
将所有路径按a升序排序，用LCT维护路径上最大的b，将边权化为点权，如果加入一条边x，其两端点分别为u,v，那么将u与i+x连边，v与i+x连边。 如果(u,v)路径最大的b值大于当前边的b，那么删去b最大的边。 注意：access操作中必须pushup，因为这个调了好久
/* User:Small Language:C++ Problem No.:3 */ #include<bits/stdc++.h> #define ll long long #define inf 99999999 using namespace std; const int M=200005; int n,m,pre[M],fa[M],ch[M][2],val[M],mx[M],stk[M],ans=inf; bool rev[M]; struct edge{ int u,v,a,b; bool operator<(const edge &y)const{ return a<y.a; } }e[M]; bool isroot(int x){ return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x; } bool get(int x){ return ch[fa[x]][1]==x; } void pushup(int rt){ int &l=ch[rt][0],&r=ch[rt][1]; mx[rt]=rt; if(val[mx[l]]>val[mx[rt]]) mx[rt]=mx[l]; if(val[mx[r]]>val[mx[rt]]) mx[rt]=mx[r]; } void pushdown(int rt){ int &l=ch[rt][0],&r=ch[rt][1]; if(rev[rt]){ rev[rt]^=1; rev[l]^=1; rev[r]^=1; swap(l,r); } } void rotate(int x){ int y=fa[x],z=fa[y],side=get(x); if(!isroot(y)) ch[z][ch[z][1]==y]=x; fa[x]=z; ch[y][side]=ch[x][side^1]; fa[ch[y][side]]=y; ch[x][side^1]=y; fa[y]=x; pushup(y); pushup(x); } void splay(int x){ int tp=0; stk[++tp]=x; for(int u=x;!isroot(u);u=fa[u]) stk[++tp]=fa[u]; while(tp) pushdown(stk[tp--]); while(!isroot(x)){ int y=fa[x]; if(!isroot(y)) rotate(get(x)==get(y)?y:x); rotate(x); } } void access(int x){ int t=0; for(int t=0;x;t=x,x=fa[x]){ splay(x); ch[x][1]=t; pushup(x); } } void makeroot(int x){ access(x); splay(x); rev[x]^=1; } void link(int x,int y){ makeroot(x); fa[x]=y; splay(x); } void cut(int x,int y){ makeroot(x); access(y); splay(y); fa[x]=ch[y][0]=0; } int query(int x,int y){ makeroot(x); access(y); splay(y); return mx[y]; } int find(int x){ return x==pre[x]?x:pre[x]=find(pre[x]); } int main(){ freopen("data.in","r",stdin);// ios::sync_with_stdio(false); cin>>n>>m; for(int i=1;i<=n;i++) pre[i]=i; for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].a>>e[i].b; sort(e+1,e+m+1); for(int i=1;i<=m;i++){ int u=e[i].u,v=e[i].v; if(find(u)==find(v)){ int t=query(u,v); if(val[t]<=e[i].b) continue; cut(t,e[t-n].u); cut(t,e[t-n].v); } else pre[find(u)]=find(v); val[i+n]=e[i].b; mx[i+n]=i+n; link(u,i+n); link(v,i+n); if(find(1)==find(n)) ans=min(ans,e[i].a+val[query(1,n)]); } if(ans==inf) ans=-1; cout<<ans<<endl; return 0; }