UOJ #3.[NOI2014]魔法森林 | Kyons'Blog 


 




UOJ #3.[NOI2014]魔法森林

发表于 | 分类于 | | 阅读次数:

序言

$UOJ$果然是神仙$OJ$啊
里面个个都是人才,说话还好听
题目的$hack$数据还可以$hack$掉网上一大片的题解…..

题目描述

为了得到书法大家的真传，小$E$同学下定决心去拜访住在魔法森林中的隐士。魔法森林可以被看成一个包含个$N$节点$M$条边的无向图，节点标号为$1…n$，边标号为$1…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$型守护精灵的个数之和。

题目大意:
从$1$走到$n$,$m$条边,如何走能使$a$和$b$的和最大值最小.

解析

首先,这是一个最小生成树的题目.
其次,这应该是一个动态最小生成树的题目.
(如果你学过用LCT做最小生成树,这个题就非常的水)
我们将$a_i$排序后,按边取,可以保证$a_i$是最小的.
在按$a_i$大小取边的时候,同时更新路上$b_i$的最大值.
当我们取到一个环的时候怎么办?
列如这样:
1
我们就要对新加入的边上$b_i$的值,和维护的链上$b_i$的最大值进行比较.

  1. 如果链上的值大,那么我们把链上最大的那条边$cut$,如何把新边连上.
  2. 如果新边大,我们便直接跳过.

如此往复,直到$1$$n$这条路连通.
连通后,我们加入另一个操作:
判断,加入的这条边对于答案的影响.$a$大并不代表$b$也大,因为问的是$a+b$的和.
直到遍历完所有边.
~过了最小生成树的代码居然只有97~~

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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long ll;

const int INF = 1e9;
const int MAXN = 2e5 + 10;

struct node {
    int x, y, a, b;
    bool operator < (const node &rhs) const {
        return a < rhs.a;
    }
}edge[MAXN];

struct vec {
    int fa, son[2];
    bool rev;
    int maxx, id;
}p[MAXN];
int n;

int isroot(int x) {
    return p[p[x].fa].son[0] != x && p[p[x].fa].son[1] != x;
}
void pushup(int x) {
    int A = p[x].id, B = p[p[x].son[0]].maxx, C = p[p[x].son[1]].maxx;
    if (edge[A].b >= edge[B].b&&edge[A].b >= edge[C].b)
        p[x].maxx = A;
    else if (edge[B].b >= edge[C].b)
        p[x].maxx = B;
    else
        p[x].maxx = C;
}
void pushdown(int x) {
    if (p[x].rev) {
        int l = p[x].son[0], r = p[x].son[1];
        swap(p[l].son[0], p[l].son[1]), p[l].rev ^= 1;
        swap(p[r].son[0], p[r].son[1]), p[r].rev ^= 1;
        p[x].rev ^= 1;
    }
}
int get(int x) {
    return p[p[x].fa].son[1] == x;
}
void rotate(int x) {
    int y = p[x].fa, t = p[y].fa, f = get(x), k = p[x].son[f ^ 1];
    p[p[k].fa = y].son[f] = p[x].son[f ^ 1];
    p[x].fa = t;
    if (!isroot(y))
        p[t].son[get(y)] = x;
    p[p[y].fa = x].son[f ^ 1] = y;
    pushup(y);
}
int top, stk[MAXN];
void splay(int x) {
    stk[top = 1] = x;
    for (int i = x; !isroot(i); i = p[i].fa)
        stk[++top] = p[i].fa;
    while (top)
        pushdown(stk[top--]);
    for (; !isroot(x); rotate(x))
        if (!isroot(p[x].fa))
            rotate(get(x) ^ get(p[x].fa) ? x : p[x].fa);
    pushup(x);
}
void access(int x) {
    for (int i = 0; x; x = p[i = x].fa)
        splay(x), p[x].son[1] = i, pushup(x);
}
void makeroot(int x) {
    access(x);
    splay(x);
    p[x].rev ^= 1;
    swap(p[x].son[0], p[x].son[1]);
}
int findroot(int x) {
    access(x); splay(x);
    while (p[x].son[0])
        pushdown(x), x = p[x].son[0];
    splay(x);
    return x;
}
void split(int x, int y) {
    makeroot(x);
    access(y);
    splay(y);
}
int link(int x, int y) {
    makeroot(x);
    if (findroot(y) == x)
        return false;
    p[x].fa = y;
    return true;
}
void Cut(int x, int y) {
    split(x, y);
    if (p[y].son[0] == x)
        p[x].fa = p[y].son[0] = 0;
}

void Addedge(int id) {
    int x = edge[id].x, y = edge[id].y;
    if (findroot(x) != findroot(y))
        link(x, id + n), link(id + n, y);
    else {
        split(x, y);
        if (edge[p[y].maxx].b > edge[id].b) {
            int tmp = p[y].maxx;
            Cut(edge[tmp].x, tmp + n), Cut(tmp + n, edge[tmp].y);
            link(edge[id].x, id + n), link(id + n, edge[id].y);
        }
    }
}
int main() {
    int m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        cin >> edge[i].x >> edge[i].y >> edge[i].a >> edge[i].b;

    sort(edge + 1, edge + m + 1);
    for (int i = 1; i <= m; i++)
        p[i + n].maxx = p[i + n].id = i;

    int ans = INF;
    for (int i = 1; i <= m; i++) {
        Addedge(i);
        while (edge[i].a == edge[i + 1].a)
            Addedge(++i);
        if (findroot(1) == findroot(n)) {
            split(1, n);
            ans = min(ans, edge[p[n].maxx].b + edge[i].a);
        }
    }

    printf("%d\n", ans == INF ? -1 : ans);

    //system("pause");
    return 0;
}







 




 


 


 

 //删除Valine核心代码库外链调用 //调用刚下载的本地文件以加速加载速度 //这里改为从本地加载