By

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3669

Solution

先按A[i]排序然后一条一条加入生成树中，然后用LCT维护生成树链上最大的B[i]，设当前加入边为{u,v}，
若u，v不连通，连接u，v
若u，v联通，找到u，v链上最大的B[i]，如果比当前边的B[i]大，则断开u，v，接上当前边，否则跳过。
每加入一条边判断1，n是否联通，更新答案。

Code 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll int
#define N 200005
#define M 100005
#define inf 100000000
using namespace std;
inline ll read(){
    char ch=getchar(); ll x=0,f=1;
    while (ch>'9'||ch<'0'){if (ch=='-') f=-1; ch=getchar();}
    while (ch<='9'&&ch>='0'){x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
inline void write(ll x){
    if (x<0) x=-x,putchar('-');
    if (x>9) write(x/10); putchar(x%10+'0');
}
inline void writeln(ll x){
    write(x); putchar('\n');
}
struct edge{
    ll u,v,a,b;
    bool friend operator <(edge x,edge y){return x.a<y.a;}
}e[M];
ll maxx[N],rev[N],left[N],right[N],fa[N],father[N],q[N],num[N];
ll n,m,top,ans=inf;
void updata(ll x){
    maxx[x]=x;
    if (num[maxx[left[x]]]>num[maxx[x]]) maxx[x]=maxx[left[x]];
    if (num[maxx[right[x]]]>num[maxx[x]]) maxx[x]=maxx[right[x]]; 
}
void pushdown(ll x){
    if (rev[x]){
        rev[x]^=1; rev[left[x]]^=1; rev[right[x]]^=1;
        swap(left[x],right[x]);
    }
}
bool isroot(ll x){
    return left[fa[x]]!=x&&right[fa[x]]!=x;
}
void rotate(ll x){
    ll y=fa[x],z=fa[y],flag=left[y]==x;
    if (!isroot(y)) if (left[z]==y) left[z]=x; else right[z]=x;
    fa[x]=z; fa[y]=x;
    if (flag) fa[left[y]=right[x]]=right[x]=y;
    else fa[right[y]=left[x]]=left[x]=y;
    updata(y); updata(x);
}
void splay(ll x){
    q[++top]=x;
    for (ll i=x;!isroot(i);i=fa[i]) q[++top]=fa[i];
    while (top) pushdown(q[top--]);
    while (!isroot(x)){
        ll y=fa[x],z=fa[y];
        if (!isroot(y)) if (left[z]==y^left[y]==x) rotate(x);
                        else rotate(y);
        rotate(x);
    }
}
void access(ll x){
    for (ll y=0;x;y=x,x=fa[x])
        splay(x),right[x]=y,updata(x);
}
void makeroot(ll x){
    access(x); splay(x); rev[x]^=1;
}
void link(ll x,ll y){
    makeroot(x); fa[x]=y; splay(x);
}
void cut(ll x,ll y){
    makeroot(x); access(y); splay(y); fa[x]=left[y]=0;
}
ll find(ll x){
    return father[x]==x?x:father[x]=find(father[x]);
}
ll query(ll x,ll y){
    makeroot(x); access(y); splay(y);
    return maxx[y];
}
int main(){
    n=read(); m=read();
    for (ll i=1;i<=m;i++){
        e[i].u=read(); e[i].v=read();
        e[i].a=read(); e[i].b=read();
    }
    sort(e+1,e+1+m);
    for (ll i=1;i<=n;i++) father[i]=i;
    for (ll i=1;i<=m;i++) num[n+i]=e[i].b;
    for (ll i=1;i<=m;i++){
        ll u=find(e[i].u),v=find(e[i].v);
        if (u!=v){
            link(e[i].u,n+i);
            link(n+i,e[i].v);
            father[u]=v;
        }else{
            ll tmp=query(e[i].u,e[i].v);
            if (num[tmp]>e[i].b){
                cut(e[tmp-n].u,tmp);
                cut(tmp,e[tmp-n].v);
                link(e[i].u,i+n);
                link(i+n,e[i].v);
            }
        }
        if (find(1)==find(n)){
            ans=min(ans,num[query(1,n)]+e[i].a);
        }
    }
    if (ans==inf) puts("-1");
    else writeln(ans);
}
文章目录
  1. 1. Solution
  2. 2. Code