BZOJ 3669
题意：给定$n$点$m$边无向图，每条边有一个边权$(a, b)$，能经过某条边当且仅当当前的$A \leq a, B \leq b$，试确定$A,B$，使得能从$1$走到$n$。
第一眼以为二分套二分，但是这题二分后再二分没有单调性了…但是还是能拿到$65$分
贪心两者和最小：将前者排序后，在不大于前者的情况下，让后者尽量小。
那么将边按照$a$排序，然后我们想想怎么样能让$b$最小。
显然一条路径最长边最小的路径在当前图的最小瓶颈生成树上，那么这里就是动态维护一个最小生成树
即，若两点不连通，则直接连边；否则将路径上的最大边删除加入这条边(或者这条边比较小不用动任何东西)
那么 LCT 维护路径。注意重边和自环。
这里边权可以变成点权，是个经典套路
注意Splay后所有的信息都不能再用之前的，变量改变后不要再用，要留意变量是否会在中途改变，会的话开临时数组存储 (特别是用了一个值之前调用了一个函数，这个函数可能改变这个值)！！！
知识点：
1、边权变点权 (网络流常用技巧)
2、Splay后所有的信息都不能再用之前的，变量改变后不要再用，要留意变量是否会在中途改变，会的话开临时数组存储 (特别是用了一个值之前调用了一个函数，这个函数可能改变这个值)
3、贪心两者和最小：将前者排序后，在不大于前者的情况下，让后者尽量小。
4、注意重边自环
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
#define lc ch[x][0]
#define rc ch[x][1]
const int MAXN = 200000 + 5, INF = 1000000000;
struct edge {
int x, y, a, b;
bool operator < (const edge &rhs) const {
return a == rhs.a ? b < rhs.b : a < rhs.a;
}
} ed[100000 + 5];
int n, m;
int val[MAXN], ch[MAXN][2], fa[MAXN], rev[MAXN], maxv[MAXN], id[MAXN];
int top, stk[MAXN];
int isRt(int x) {return ch[fa[x]][0] != x && ch[fa[x]][1] != x;} //???Splay???
int rel(int x) {return ch[fa[x]][1] == x;} // ? Splay
void prorev(int x) {swap(lc, rc), rev[x] ^= 1;} // ?????? (????)
void pushup(int x) {
maxv[x] = val[x], id[x] = x;
if (maxv[x] < maxv[lc])
maxv[x] = maxv[lc], id[x] = id[lc];
if (maxv[x] < maxv[rc])
maxv[x] = maxv[rc], id[x] = id[rc];
}
void pushdown(int x) { //????
if (rev[x]) {
if (lc) prorev(lc);
if (rc) prorev(rc);
rev[x] = 0;
}
}
void rotate(int x) { // ? Splay
pushdown(fa[x]), pushdown(x);
int y = fa[x], z = fa[y], k = rel(x), w = ch[x][k ^ 1];
if (!isRt(y)) ch[z][rel(y)] = x;
fa[x] = z; // y ??? (z, y) ???,???? (??? Splay ???? 1)
ch[y][k] = w, fa[w] = y;
ch[x][k ^ 1] = y, fa[y] = x;
pushup(y), pushup(x);
}
void splay(int x) { // ? Splay
//printf("%d\n", x);
top = 0;
stk[++top] = x;
for (int pos = x; !isRt(pos); pos = fa[pos]) stk[++top] = fa[pos];
while (top) pushdown(stk[top--]); // ? x ?????????????? pushdown (??? Splay ???? 2)
//???1:???? isRt ???,????pushdown
while (!isRt(x)) { // (??? Splay ???? 3.1)
int y = fa[x];
if (!isRt(y)) { // (??? Splay ???? 3.2)
if (rel(x) == rel(y)) rotate(y); else rotate(x);
}
rotate(x);
}
//pushup(x); ??????
}
void access(int x) { // ????? x ???????????,??? x ????????????????
for (int y = 0; x; y = x, x = fa[x])
splay(x), rc = y, pushup(x);
}
void makeRt(int x) { // ??????
access(x), splay(x);
prorev(x);
}
int findRt(int x) { // ????? x ??
access(x), splay(x);
while (pushdown(x), lc) x = lc;
splay(x); // splay ????
return x;
}
void split(int x, int y) { // ???????? x-y
makeRt(x);
access(y), splay(y); // splay ????
//???2:?(x)?y??????,???? access ??,y ??????,?????
}
void link(int x, int y) { // ?????? x-y
makeRt(x);
if (findRt(y) != x) fa[x] = y;
}
void cut(int x, int y) { // ?????? x-y
makeRt(x);
if (findRt(y) == x && fa[y] == x && !ch[y][0]) {
fa[y] = rc = 0;
pushup(x);
}
//split(x, y), fa[x] = ch[y][0] = 0, pushup(y);
}
void clean() {
ms(val, 0), ms(ch, 0), ms(fa, 0), ms(rev, 0), ms(maxv, 0), ms(id, 0);
}
int solve() {
clean();
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i) scanf("%d%d%d%d", &ed[i].x, &ed[i].y, &ed[i].a, &ed[i].b);
sort(ed + 1, ed + 1 + m);
for (int i = 1; i <= m; ++i) val[i + n] = ed[i].b;
int ans = INF;
for (int i = 1; i <= m; ++i) {
int &u = ed[i].x, &v = ed[i].y;
if (u == v) continue ;
if (findRt(u) == findRt(v)) {
split(u, v);
if (val[id[v]] <= ed[i].b) {
if (findRt(1) == findRt(n)) {
split(1, n);
ans = min(ans, ed[i].a + maxv[n]);
}
continue ;
}
int whw = id[v]; // 一定要这样！！id会变化！！
cut(whw, ed[whw - n].x);
cut(whw, ed[whw - n].y);
link(u, i + n);
link(v, i + n);
} else {
link(u, i + n);
link(v, i + n);
}
if (findRt(1) == findRt(n)) {
split(1, n);
ans = min(ans, ed[i].a + maxv[n]);
}
}
if (ans == INF) cout << -1; else cout << ans;
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
/*
4 6
2 4 2 9
4 3 4 6
2 3 6 5
4 4 9 9
4 1 7 7
1 3 7 4
4 4
1 3 7 4
4 3 4 6
2 3 6 5
2 4 2 9
4 6
2 3 8 10
4 1 9 9
2 1 7 8
3 1 7 7
4 3 10 5
3 1 2 10
4 3
4 1 9 9
3 1 7 7
4 3 10 5
*/
