【题目描述】

题目描述又臭又长

简单来说 有一个有$n$个点,$m$条边的无向图,每条边有两个权值$a,b$,从点$u$走到任意一个点$v$的代价是途经的边中最大的$a$加上最大的$b$

求从点$1$到点$n$的最小代价

【输入格式】

rt,给你一张图

【输出格式】

输出最小代价。如果无法到达,输出-1

题解

如果边权只有一个,那么显然就是建出最小生成树

但是这里有两个 我们可以先以$a$为关键字给所有边从小到大排序 然后依次把每条边加入

这里就和最小生成树有些异曲同工之妙相似

假设加入的这条边是$(u,v)$,如果$u,v$还未联通就直接给它连上

如果已经联通了 我们就检查一下现在的$u\rightarrow v$这条链上面$b$最大的一条边 如果那条边的$b$比$(u,v)$的$b$大 那就把那条边割掉 把$(u,v)$这条边给连上

这个就可以用LCT来维护

求$b$最大的边只需要在splay上维护一下 然后split(u,v)就能找到

每次加完边后 如果$1$与$n$联通 就更新一下答案

$1\rightarrow n$路径上最大的$b$已知 那最大的$a$呢?

最大的$a$直接用这次加入的边的$a$即可

因为如果这次加入的边不在$1\rightarrow n$的路径上 那么在这条路径第一次在树上出现时就应该已经用正确的$a$更新过了

复杂度$O(n\log n)$

这道题可以不用findroot来判联通。。。但是懒得写了

代码

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
#include <bits/stdc++.h>
#define N 200005
using namespace std;

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

struct edge{
int u, v, a, b;

friend bool operator < (edge x, edge y) {
return x.a < y.a;
}
} e[N];

int ch[N][2], fa[N], mx[N], val[N], tag[N];

#define lson ch[x][0]
#define rson ch[x][1]

inline void pushup(int x) {
mx[x] = x;
if (val[mx[lson]] > val[mx[x]]) mx[x] = mx[lson];
if (val[mx[rson]] > val[mx[x]]) mx[x] = mx[rson];
}

inline void rev(int x) {
swap(lson, rson);
tag[x] ^= 1;
}

inline void pushdown(int x) {
if (tag[x]) {
if (lson) rev(lson);
if (rson) rev(rson);
tag[x] = 0;
}
}

inline bool isroot(int x) {
return ch[fa[x]][0] != x && ch[fa[x]][1] != x;
}

inline void rotate(int x) {
int y = fa[x], z = fa[y], k = (ch[y][1] == x);
if (!isroot(y)) ch[z][ch[z][1]==y] = x;
fa[x] = z;
ch[y][k] = ch[x][k^1]; fa[ch[x][k^1]] = y;
ch[x][k^1] = y; fa[y] = x;
pushup(y); pushup(x);
}

int q[N], top;

inline void splay(int x) {
q[top=1] = x;
for (int i = x; !isroot(i); i = fa[i]) q[++top] = fa[i];
while (top) pushdown(q[top--]);
while (!isroot(x)) {
int y = fa[x], z = fa[y];
if (!isroot(y)) {
((ch[z][0] == y) ^ (ch[y][0] == x)) ? rotate(x) : rotate(y);
}
rotate(x);
}
}

inline void access(int x) {
for (int i = 0; x; i = x, x = fa[x]) {
splay(x), ch[x][1] = i, pushup(x);
}
}

inline void makeroot(int x) {
access(x), splay(x), rev(x);
}

inline void link(int x, int y) {
makeroot(x);
fa[x] = y;
}

inline void split(int x, int y) {
makeroot(x), access(y), splay(y);
}

inline int findroot(int x) {
access(x), splay(x);
while (lson) pushdown(x), x = lson;
splay(x);
return x;
}

inline void cut(int x, int y) {
split(x, y);
if (ch[y][0] == x && !ch[x][1]) {
ch[y][0] = fa[x] = 0;
}
}

int n, m, ans;

int main() {
n = read(), m = read();
ans = 0x7fffffff;
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 + m + 1);
for (int i = 1; i <= m; i++) {
val[n + i] = e[i].b;
}
for (int i = 1; i <= m; i++) {
bool lk = 1;
if (findroot(e[i].u) == findroot(e[i].v)) {
split(e[i].u, e[i].v);
int mxnow = mx[e[i].v];
if (val[mxnow] > e[i].b) {
cut(e[mxnow-n].u, mxnow); cut(e[mxnow-n].v, mxnow);
} else lk = 0;
}
if (lk) {
link(e[i].u, i + n); link(e[i].v, i + n);
}
if (findroot(1) == findroot(n)) {
split(1, n);
ans = min(ans, e[i].a + val[mx[n]]);
}
}
printf("%d\n", ans == 0x7fffffff ? -1 : ans);
return 0;
}

评论