「BZOJ3669」[NOI2014]魔法森林

Description

为了得到书法大家的真传,小 E 同学下定决心去拜访住在魔法森林中的隐士。

魔法森林可以被看成一个包含 NN 个节点 MM 条边的无向图,节点标号为 1,,N1,\ldots,N,边标号为 1,,M1,\ldots,M。初始时小 E 同学在号节点 11,隐士则住在 NN 号节点。小 E 需要通过这一片魔法森林,才能够拜访到隐士。

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

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

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

Input

第一行包含两个整数 N,MN,M,表示无向图共有 NN 个节点,MM 条边。
接下来 MM 行,第 ii 行包含四个正整数 Xi,Yi,Ai,BiX_i,Y_i,A_i,B_i,描述第 ii 条无向边。其中 XiX_iYiY_i 为该边两个端点的标号,AiA_iBiB_i 的含义如题所述。

注意:数据中可能包含重边与自环。

Output

输出一行一个整数:如果小 E 可以成功拜访到隐士,输出小 E 最少需要携带的守护精灵的总个数;
如果无论如何小 E 都无法拜访到隐士,输出 “-1”(不含引号)。

Sample Input

1
2
3
4
5
6
4 5
1 2 19 1
2 3 8 12
2 4 12 15
1 3 17 8
3 4 1 17

Sample Output

1
32

HINT

如果小 E 走路径 1241\rightarrow2\rightarrow4,需要携带 19+15=3419+15=34 个守护精灵;
如果小 E 走路径 1341\rightarrow3\rightarrow4,需要携带 17+17=3417+17=34 个守护精灵;
如果小 E 走路径 12341\rightarrow2\rightarrow3\rightarrow4,需要携带 19+17=3619+17=36 个守护精灵;
如果小 E 走路径 13241\rightarrow3\rightarrow2\rightarrow4,需要携带 17+15=3217+15=32 个守护精灵。
综上所述,小 E 最少需要携带 3232 个守护精灵。

对所有的数据,2n50000, 0m100000, 1ai,bi500002 \leq n \leq 50000,\ 0 \leq m \leq 100000,\ 1 \leq a_i ,b_i \leq 50000

Solution

两维的问题先把边按照aia_i从小到大排序。
然后维护最小瓶颈生成树,遍历每一条边(x,y)(x,y)

  • 若它构成了环,找到(x,y)(x,y)路径上bib_i权值最小的边的编号,如果这个边bib_i小于当前边,那么跳过,否则就删了那条边,改成当前边。
  • 否则就直接连边

枚举加入到第ii条边,意味着钦定了aia_i的最大值是当前边,那么就要一方面看11nn是否连通,若连通就要找到1n1\to n里的边最大值bib_i,此时aia_ibib_i相加就是答案了。

如果当前边连上11nn就联通了,那么以后findroot(x)=findroot(y)findroot(x)=findroot(y)就会成立,但除非1n1\to n的路径上出现更小的bib_i,否则因为aia_i在递增,就不会影响答案。

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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}

const int N = 51000 + 210000, M = 210000;
int n, m;
struct Edge {
int u, v, w1, w2;
}e[M*2];
bool cmp(Edge _x, Edge _y) {
return _x.w1 < _y.w1;
}
struct LinkCut{
int ch[N][2], tot;
int fa[N], val[N], c[N];
bool ident(int x) {
return ch[fa[x]][1] == x;
}
bool nr(int x) {
return ch[fa[x]][0] == x || ch[fa[x]][1] == x;
}
void con(int x, int F, int how) {
ch[F][how] = x;
fa[x] = F;
}
bool r[N];
void down(int x) {
if(r[x]) {
r[x] = 0;
r[ch[x][0]] ^= 1;
r[ch[x][1]] ^= 1;
swap(ch[x][0], ch[x][1]);
}
}
void up(int x) {
if(e[val[ch[x][0]]].w2 > e[val[ch[x][1]]].w2)
val[x] = val[ch[x][0]];
else
val[x] = val[ch[x][1]];
if(e[c[x]].w2 > e[val[x]].w2)
val[x] = c[x];
}
void rotate(int x) {
if(ident(x)) {
int y = fa[x];
int z = ch[x][0];
fa[x] = fa[y];
if(nr(y))
con(x, fa[y], ident(y));
con(y, x, 0);
con(z, y, 1);
up(y); up(x);
} else {
int y = fa[x];
int z = ch[x][1];
fa[x] = fa[y];
if(nr(y))
con(x, fa[y], ident(y));
con(z, y, 0);
con(y, x, 1);
up(y);up(x);
}
}
int st[N], top;
void splay(int x) {
top = 0;
int y = x;
while(nr(y)) st[++top] = y, y = fa[y];
st[++top] = y;
while(top) down(st[top--]);
for(y = fa[x]; nr(x); y = fa[x]) {
if(nr(y)) rotate(ident(x) == ident(y) ? y : x);
rotate(x);
}
}
void access(int x) {
for(int y = 0; x; x = fa[y = x])
splay(x), ch[x][1] = y, up(x);
}
int findroot(int x) {
access(x);
splay(x);
while(ch[x][0]) x = ch[x][0];
return x;
}
void makeroot(int x) {
access(x);
splay(x);
r[x] ^= 1;
}
void link(int x, int y) {
makeroot(y);
if(findroot(x) == y) return;
fa[y] = x;
}
void cut(int x, int y) {
makeroot(x);
if(findroot(y) != x || ch[y][0] != x || fa[x] != y || ch[x][1]) return;
fa[x] = ch[y][0] = 0;
}
int query(int x, int y) {
makeroot(x);
access(y);
splay(y);
return val[y];
}
}lct;
int main() {
n = read(), m = read();
for(int i = 1; i <= m; ++i) {
e[i].u = read();
e[i].v = read();
e[i].w1 = read();
e[i].w2 = read();
}
sort(e + 1, e + 1 + m, cmp);
int ans = 1e9;
for(int i = 1; i <= m; ++i) {
int x = e[i].u, y = e[i].v;
if(x == y) continue;
if(lct.findroot(x) == lct.findroot(y)) {
int b = lct.query(x, y);
if(e[b].w2 <= e[i].w2) continue;
lct.cut(b + n, e[b].u);
lct.cut(b + n, e[b].v);
}
lct.val[i + n] = lct.c[i + n] = i;
lct.link(i + n, x);
lct.link(i + n, y);
if(lct.findroot(1) == lct.findroot(n)) {
int b = lct.query(1, n);
ans = min(ans, e[i].w1 + e[b].w2);
}
}
if(ans == 1e9) puts("-1");
else
writeln(ans);
return 0;
}