Solution
非常妙的排序啊。。。
仔细想想好像确实能够找出最优解QUQ
先对第一关键字排序, 在$LCT$ 维护第二关键字的最大值 所在的边。
添边时如果$u, v$ 不连通 就直接加边。 如果连通 并且路径上的最大值 大于 当前边 的 第二关键字, 那么可以换掉。
如果 $1$ 和 $N$ 连通 就 更新答案。
这样就可以保证 在 所有路径上的边 第一关键字 小于等于 当前边 的第一关键字的前提下, 第二关键字的 最大值 最小。
除了这一点不一样, 其他就是模板了。
Code
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define rd read() 5 using namespace std; 6 7 const int N = 1e5 + 5; 8 const int inf = ~0U >> 2; 9 10 int n, m; 11 int ans = inf; 12 13 struct edge { 14 int u, v, a, b; 15 }e[N << 1]; 16 17 int read() { 18 int X = 0, p = 1; char c = getchar(); 19 for (; c > '9' || c < '0'; c = getchar()) 20 if (c == '-') p = -1; 21 for (; c >= '0' && c <= '9'; c = getchar()) 22 X = X * 10 + c - '0'; 23 return X * p; 24 } 25 26 int cmp(const edge &A, const edge &B) { 27 return A.a < B.a; 28 } 29 30 void cmin(int &A, int B) { 31 if (A > B) 32 A = B; 33 } 34 35 namespace LCT { 36 int val[N << 1], f[N << 1], ch[N << 1][2], mx[N << 1], tun[N << 1]; 37 #define lc(x) ch[x][0] 38 #define rc(x) ch[x][1] 39 40 int isroot(int x) { 41 return lc(f[x]) != x && rc(f[x]) != x; 42 } 43 44 int get(int x) { 45 return rc(f[x]) == x; 46 } 47 48 void up(int x) { 49 mx[x] = val[x]; 50 if (e[mx[lc(x)]].b > e[mx[x]].b) mx[x] = mx[lc(x)]; 51 if (e[mx[rc(x)]].b > e[mx[x]].b) mx[x] = mx[rc(x)]; 52 } 53 54 void rev(int x) { 55 swap(lc(x), rc(x)); 56 tun[x] ^= 1; 57 } 58 59 void pushdown(int x) { 60 if (tun[x]) { 61 if (lc(x)) rev(lc(x)); 62 if (rc(x)) rev(rc(x)); 63 tun[x] = 0; 64 } 65 } 66 67 int st[N << 1], tp; 68 69 void pd(int x) { 70 while (!isroot(x)) { 71 st[++tp] = x; 72 x = f[x]; 73 } 74 pushdown(x); 75 while (tp) pushdown(st[tp--]); 76 } 77 78 void rotate(int x) { 79 int old = f[x], oldf = f[old], son = ch[x][get(x) ^ 1]; 80 if (!isroot(old)) ch[oldf][get(old)] = x; 81 ch[x][get(x) ^ 1] = old; 82 ch[old][get(x)] = son; 83 f[old] = x; f[son] = old; f[x] = oldf; 84 up(old); up(x); 85 } 86 87 void splay(int x) { 88 pd(x); 89 for (; !isroot(x); rotate(x)) 90 if (!isroot(f[x])) 91 rotate(get(f[x]) == get(x) ? f[x] : x); 92 } 93 94 void access(int x) { 95 for (int y = 0; x; y = x, x = f[x]) 96 splay(x), ch[x][1] = y, up(x); 97 } 98 99 void mroot(int x) { 100 access(x); splay(x); rev(x); 101 } 102 103 void split(int x, int y) { 104 mroot(x); access(y); splay(y); 105 } 106 107 int findr(int x) { 108 access(x); splay(x); 109 while(lc(x)) pushdown(x), x = lc(x); 110 return x; 111 } 112 113 void link(int x, int y) { 114 mroot(x); f[x] = y; 115 } 116 117 void cut(int x, int y) { 118 split(x, y); 119 f[x] = ch[y][0] = 0; 120 } 121 } 122 using namespace LCT; 123 124 int main() 125 { 126 n = rd; m = rd; 127 for (int i = 1; i <= m; ++i) { 128 e[i].u = rd; e[i].v = rd; 129 e[i].a = rd; e[i].b = rd; 130 } 131 sort(e + 1, e + 1 + m, cmp); 132 for (int i = 1; i <= m; ++i) 133 val[i + n] = i; 134 for (int i = 1; i <= m; ++i) { 135 int x = e[i].u, y = e[i].v, t; 136 if (x == y) continue; 137 mroot(x); 138 if (findr(y) != x) 139 link(i + n, x), link(i + n, y); 140 else if (e[t = mx[y]].b > e[i].b) 141 cut(t + n, e[t].u), cut(t + n, e[t].v), 142 link(i + n, x), link(i + n, y); 143 mroot(1); 144 if (findr(n) == 1) 145 cmin(ans, e[i].a + e[mx[n]].b); 146 } 147 printf("%d\n", ans == inf ? -1 : ans); 148 }