Fork me on GitHub

「NOI2014」魔法森林

发表于 | 分类于
字数统计: 1,042字 | 阅读时长 ≈ 6分钟

NOI2014-魔法森林

Links there:NOI2014MogicForest

题意:给出一个无向图,每一条边有两个权值$A_i,B_i$

要求从$1$节点跑到$n$节点的可能路径上,求出最小的$A_i+B_i$

思路:

首先对边进行排序,很显然的针对某个变量($A$或者$B$)关键字排序.

然后用$LCT$动态维护一个MST.每次找边的时候,如果两个点已经连结,那么在该换上找到最大值并换成次大值,特别的,如果1,n联通,则说明有路径存在,我们更新答案.这样就做到了动态维护.

上述为正常$LCT$做法.

但是听大爷们讲这题可以用$SPFA$的$O(玄学)$复杂度水掉.

个人感觉其实如果数据出的比较强的话可以卡掉$SPFA$的,但是估计出题人也没想到那么多吧…

（md调了半天一个pushup写错了）

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
//my vegetable has exploded. :(
#include<bits/stdc++.h>
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define MM(x,y) memset(x,y,sizeof(x))
#define MCPY(a,b) memcpy(a,b,sizeof(b))
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=b;i>=a;i--)
#define fi first
#define se second
using namespace std;
#define lc ch[u][0]
#define rc ch[u][1]

const int INF = 0x3f3f3f3f;
const int MAXN = 5e4+10;
const int MAXM = 1e5+10;
inline int quickpow(int m,int n,int p){int b=1;while(n){if(n&1)b=b*m%p;n=n>>1;m=m*m%p;}return b;}
inline int getinv(  int x,int p){return quickpow(x,p-2,p);}
inline int read(void){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){f=ch=='-'?-1:1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x * f;
}
int n,m,F[MAXN<<1];
int getf(int x){return x==F[x]?x:F[x]=getf(F[x]);}
struct Edges{
    int u,v,A,B;
    inline bool operator < (const Edges &b) const {
        return (A==b.A)?(B<b.B):A<b.A;
    }
    inline void Rd(void){u=read(),v=read(),A=read(),B=read();}
}E[MAXM<<1];
struct LinkCutTree{
    int ch[MAXN<<2][2],fa[MAXN<<2],rev[MAXN<<2],sum[MAXN<<2],mx[MAXN<<2],w[MAXN<<2];
    inline bool isRson(int u){return ch[fa[u]][1] == u;}
    inline bool isRoot(int u){return (ch[fa[u]][0] != u && ch[fa[u]][1] != u);}
    inline void Reverse(int u){rev[u] ^= 1;swap(lc,rc);}
    inline void pushdown(int u){if(rev[u]){if (lc) Reverse(lc); if(rc)Reverse(rc); rev[u]=0;}}
    inline void pushup(int u){
        mx[u]=u;
        mx[u]=w[mx[u]]<w[mx[lc]]?mx[lc]:mx[u];
        mx[u]=w[mx[u]]<w[mx[rc]]?mx[rc]:mx[u];
    }
    inline void Update(int u){if (!isRoot(u)) Update(fa[u]); pushdown(u);}
/* ----------- Splay part ------------*/
    inline void rotate(int u){
        int fau = fa[u],ffau = fa[fau],d = isRson(u);
        fa[u]=ffau; if (!isRoot(fau)) ch[ffau][isRson(fau)] = u;
        fa[ch[fau][d] = ch[u][d^1]] = fau;
        fa[ch[u][d^1] = fau] = u;
        pushup(fau); pushup(u);
    }
    inline void Splay(int u){ //边Splay边向根传递信息
        Update(u);
        for (;(!isRoot(u));rotate(u)){
            if (!isRoot(fa[u]))
            rotate(isRson(fa[u])==isRson(u)?fa[u]:u);
        }
    }
/* ----------- LCT part ------------*/
    inline void access(int u){
        for(int f = 0; u; f = u,u = fa[u]){
            Splay(u);
            rc = f;
            pushup(u);
        }
    }
    inline void makeroot(int u){access(u);Splay(u);Reverse(u);}
    inline int find(int u){access(u);Splay(u);while(lc)pushdown(u),u=lc;return u;}
    inline void split(int x,int y){makeroot(x);access(y);Splay(y);}
    inline void link(int x,int y){makeroot(x);fa[x]=y;}
    inline void cut(int u,int v){split(u,v);if(fa[u]==v&&(!rc))fa[u]=ch[v][0]=0;pushup(v);}
    inline int query(int u,int v){makeroot(u);access(v);Splay(v);return mx[ch[v][0]];}
}LCT;
int ans = INF;

///------------------head------------------
signed main(signed argc, char *argv[]){
    n=read(),m=read();
    rep(i,1,m) E[i].Rd();
    sort(E+1,E+m+1);
    rep(i,1,m){
        int u=E[i].u,v=E[i].v,A=E[i].A,B=E[i].B;
        LCT.w[n+i]=B; LCT.mx[n+i] = n+i;
        if(LCT.find(u)==LCT.find(v))
        {
            int ret = LCT.query(u,v);
            if (LCT.w[ret] > B){
                LCT.cut(ret,E[ret-n].u);
                LCT.cut(ret,E[ret-n].v);
                LCT.link(u,n+i);
                LCT.link(v,n+i);
            }
        }
        else{LCT.link(u,n+i); LCT.link(v,n+i);}
        if (LCT.find(1)==LCT.find(n))
            ans = min(ans,A+LCT.w[LCT.query(1,n)]);
    }
    printf("%d\n",ans==INF?-1:ans);
    return 0;
}