【题目描述】
题目描述又臭又长
简单来说 有一个有$n$个点，$m$条边的无向图，每条边有两个权值$a,b$，从点$u$走到任意一个点$v$的代价是途经的边中最大的$a$加上最大的$b$
求从点$1$到点$n$的最小代价
【输入格式】
rt，给你一张图
【输出格式】
输出最小代价。如果无法到达，输出-1。
题解
如果边权只有一个，那么显然就是建出最小生成树
但是这里有两个 我们可以先以$a$为关键字给所有边从小到大排序 然后依次把每条边加入
这里就和最小生成树有些异曲同工之妙相似
假设加入的这条边是$(u,v)$，如果$u,v$还未联通就直接给它连上
如果已经联通了 我们就检查一下现在的$u ightarrow v$这条链上面$b$最大的一条边 如果那条边的$b$比$(u,v)$的$b$大 那就把那条边割掉 把$(u,v)$这条边给连上
这个就可以用LCT来维护
求$b$最大的边只需要在splay上维护一下 然后split(u,v)就能找到
每次加完边后 如果$1$与$n$联通 就更新一下答案
$1 ightarrow n$路径上最大的$b$已知 那最大的$a$呢？
最大的$a$直接用这次加入的边的$a$即可
因为如果这次加入的边不在$1 ightarrow n$的路径上 那么在这条路径第一次在树上出现时就应该已经用正确的$a$更新过了
复杂度$O(nlog n)$
这道题可以不用findroot来判联通。。。但是懒得写了
代码
#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
", ans == 0x7fffffff ? -1 : ans);
return 0;
}