「NOI 2014」魔法森林

发表于 | | 阅读次数:
字数统计: 1.2k 字

Description

题目链接：BZOJ 3669

为了得到书法大家的真传，小 E 同学下定决心去拜访住在魔法森林中的隐士。魔法森林可以被看成一个包含 $n$ 个节点 $m$ 条边的无向图，节点标号为 $1,2,3,\dots,n$，边标号为 $1,2,3,\dots,m$。初始时小 E 同学在 $1$ 号节点，隐士则住在 $n​$ 号节点。小 E 需要通过这一片魔法森林，才能够拜访到隐士。

魔法森林中居住了一些妖怪。每当有人经过一条边的时候，这条边上的妖怪就会对其发起攻击。幸运的是，在 $1$ 号节点住着两种守护精灵：$A$ 型守护精灵与 $B​$ 型守护精灵。小 E 可以借助它们的力量，达到自己的目的。

只要小 E 带上足够多的守护精灵，妖怪们就不会发起攻击了。具体来说，无向图中的每一条边 $E_i$ 包含两个权值 $a_i$ 与 $b_i$。若身上携带的 $A$ 型守护精灵个数不少于 $a_i$，且 $B$ 型守护精灵个数不少于 $b_i​$，这条边上的妖怪就不会对通过这条边的人发起攻击。当且仅当通过这片魔法森林的过程中没有任意一条边的妖怪向小 E 发起攻击，他才能成功找到隐士。

由于携带守护精灵是一件非常麻烦的事，小 E 想要知道，要能够成功拜访到隐士，最少需要携带守护精灵的总个数。守护精灵的总个数为 $A$ 型守护精灵的个数与 $B$ 型守护精灵的个数之和。

数据范围：$2\le n\le 5\times 10^4$，$0\le m\le 10^5$，$1\le a_i,b_i\le 5\times 10^4$

Solution

动态维护边的信息一定想到 $\text{LCT}$。我们先对 $a_i$ 按照从小到大的顺序将边排序。我们按次序加入边。假设当前边为 $(u,v,a,b)$，那么有 $2$ 种情况：

  • 点 $u$ 和 $v$ 不连通：直接加入这条边。
  • 点 $u$ 和 $v$ 联通时：如果链 $(u,v)$ 上 $b_i$ 的最大值大于 $b$，那么加入这条边，否则什么也不干。

注意每次都要判断 $1$ 到 $n$ 的连通性，如果联通就更新答案。注意无解情况。

时间复杂度：$O(m\log m)$

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
 
#include <cstdio>
#include <algorithm>
#define ls(x) ch[x][0]
#define rs(x) ch[x][1]

const int N=1.5e5+5;
int n,m,f[N],fa[N],ch[N][2],mx[N],st[N],val[N];
bool r[N];
struct Edge {
    int u,v,x,y;
    bool operator < (const Edge &b) const {
        return x<b.x;
    }
} e[N];

bool get(int x) {
    return rs(fa[x])==x;
}
bool isroot(int x) {
    return ls(fa[x])!=x&&rs(fa[x])!=x;
}
void rev(int x) {
    r[x]^=1,std::swap(ls(x),rs(x));
}
void pushup(int x) {
    mx[x]=x;
    if(ls(x)&&val[mx[ls(x)]]>val[mx[x]]) mx[x]=mx[ls(x)];
    if(rs(x)&&val[mx[rs(x)]]>val[mx[x]]) mx[x]=mx[rs(x)];
}
void pushdown(int x) {
    if(r[x]) rev(ls(x)),rev(rs(x)),r[x]=0;
}
void rotate(int x) {
    int y=fa[x],z=fa[y],k=get(x);
    !isroot(y)&&(ch[z][get(y)]=x),fa[x]=z;
    ch[y][k]=ch[x][!k],fa[ch[x][!k]]=y;
    ch[x][!k]=y,fa[y]=x;
    pushup(y),pushup(x);
}
void splay(int x) {
    int u=x,tp=0;
    st[++tp]=u;
    while(!isroot(u)) st[++tp]=u=fa[u];
    while(tp) pushdown(st[tp--]);
    while(!isroot(x)) {
        int y=fa[x];
        if(!isroot(y)) rotate(get(x)==get(y)?y:x);
        rotate(x);
    }
}
void access(int x) {
    for(int y=0;x;x=fa[y=x]) splay(x),rs(x)=y,pushup(x);
}
void makeroot(int x) {
    access(x),splay(x),rev(x);
}
void split(int x,int y) {
    makeroot(x),access(y),splay(y);
}
void link(int x,int y) {
    makeroot(x),fa[x]=y;
}
void cut(int x,int y) {
    split(x,y),fa[x]=ls(y)=0,pushup(y);
}
int find(int x) {
    return f[x]==x?x:f[x]=find(f[x]);
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i) {
        scanf("%d%d%d%d",&e[i].u,&e[i].v,&e[i].x,&e[i].y);
    }
    std::sort(e+1,e+m+1);
    for(int i=1;i<=n;++i) f[i]=i;
    for(int i=1;i<=m;++i) val[i+n]=e[i].y;
    int ans=1<<30;
    for(int i=1;i<=m;++i) {
        int u=e[i].u,v=e[i].v;
        if(u==v) continue;
        if(find(u)==find(v)) {
            split(u,v);
            int j=mx[v]-n;
            if(e[j].y<=e[i].y) continue;
            cut(e[j].u,j+n),cut(e[j].v,j+n);
            link(u,i+n),link(v,i+n);
        } else {
            f[find(u)]=find(v);
            link(u,i+n),link(v,i+n);
        }
        if(find(1)==find(n)) {
            split(1,n);
            int j=mx[n]-n;
            ans=std::min(ans,e[i].x+e[j].y);
        }
    }
    printf("%d\n",ans==1<<30?-1:ans);
    return 0;
}
0%