P2387 [NOI2014]魔法森林

发表于 | 阅读数

给出一个$n$个点，$m$条边的无向图，每条边都有权值$a_i,b_i$ ，求一条从点$1$到点$n$的路径，使得这条路径上边的$a_i,b_i$ 最大值之和最小

限制$a$的最大值，然后动态维护$b$的最小生成树即可。

代码 
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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213



#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define pii pair<int, int>
const int N = 1e6 + 10;
const int mod = 1e9 + 7;

int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0', c = getchar();
    return x * f;
}

struct LCT
{
#define ls son[pos][0]
#define rs son[pos][1]

    int fa[N], cnt[N], root, tcnt;
    pii mx[N], val[N];
    int son[N][2];
    int rev[N];
    void pushup(int pos)
    {
        mx[pos] = max(max(mx[rs], mx[ls]), val[pos]);
    }
    bool isroot(int pos)
    {
        return pos != son[fa[pos]][0] && pos != son[fa[pos]][1];
    }
    void addtag(int pos)
    {
        rev[pos] ^= 1;
        swap(son[pos][0], son[pos][1]);
    }
    void pushdown(int pos)
    {
        if (rev[pos])
        {
            if (son[pos][1])
                addtag(son[pos][1]);
            if (son[pos][0])
                addtag(son[pos][0]);
            rev[pos] = 0;
        }
    }

    bool isson(int pos) { return pos == son[fa[pos]][1]; }

    void conect(int x, int d, int y)
    {
        son[x][d] = y;
        fa[y] = x;
    }

    void rotate(int x)
    {
        int y = fa[x], z = fa[y], dx = isson(x), dy = isson(y);

        fa[x] = z;
        if (!isroot(y))
            son[z][dy] = x;
        //conect(z, dy, x);
        conect(y, dx, son[x][dx ^ 1]);
        conect(x, dx ^ 1, y);
        pushup(y), pushup(x);
    }
    int st[N];
    void splay(int x)
    {
        int top;
        st[top = 1] = x;
        int u = x;
        while (!isroot(u))
            u = fa[u], st[++top] = u;
        while (top)
            pushdown(st[top--]);
        while (!isroot(x))
        {
            int y = fa[x];
            if (isroot(y))
            {
                rotate(x);
            }
            else if (isson(x) == isson(y))
                rotate(y), rotate(x);
            else
                rotate(x), rotate(x);
        }
        pushup(x);
    }
    void access(int x)
    {

        for (int i = 0; x; i = x, x = fa[x])
        {

            splay(x), son[x][1] = i, pushup(x);
        }
    }
    void makeroot(int x)
    {
        access(x), splay(x), addtag(x); // access 之后将没有右子树。然后把x变成根，把下面都翻转，这样x就是最小的元素了。
    }
    int findroot(int x)
    {
        access(x), splay(x);
        while (son[x][0])
            pushdown(x), x = son[x][0];
        //splay(x);
        return x;
    }
    void split(int x, int y)
    {
        makeroot(x);
        access(y);
        splay(y);
    }
    bool link(int x, int y)
    {
        makeroot(x);
        if (findroot(y) == x)
            return 0; //两点已经在同一子树中，再连边不合法
        fa[x] = y;
        return 1;
    }
    bool islink(int x, int y)
    {
        makeroot(x);
        if (findroot(y) == x)
            return 1;
        else
            return 0;
    }
    bool cut(int x, int y)
    {
        makeroot(x);
        if (findroot(y) == x)
        {
            split(x, y);
            if (fa[x] == y && !son[x][1])
            {
                fa[x] = 0;
                son[y][0] = 0; //x在findroot(y)后被转到了根
                pushup(y);
            }
            return 0;
        }
        return 1;
    }

} t;

struct node
{
    int u, v, a, b;
} e[N];
int main()
{
    int n = read(), m = read();
    for (int 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, [&](node x, node y) { return x.a < y.a; });
    for (int i = 1; i <= m; i++)
        t.val[i + n] = {e[i].b, i};
    int ans = 1e9;
    for (int i = 1; i <= m; i++)
    {
        int u = e[i].u, v = e[i].v, a = e[i].a, b = e[i].b;
        if (t.islink(u, v))
        {
            t.split(u, v);
            pii o = t.mx[v];
            if (o.first > b)
            {
                t.cut(e[o.second].u, o.second + n);
                t.cut(e[o.second].v, o.second + n);
                t.link(u, i + n);
                t.link(v, i + n);
            }
        }
        else
        {
            t.link(u, i + n);
            t.link(v, i + n);
        }
        if (t.islink(1, n))
        {
            t.split(1, n);
            // cout << t.mx[n].first << endl;
            ans = min(ans, a + t.mx[n].first);
        }
    }
    if (ans == 1e9)
        cout << -1 << endl;
    else
        cout << ans << endl;
}