这道题呢,
首先按照关键字a排序,然后不断地加边,用lct维护这个过程
具体实现: 先按照关键字a排序,枚举每一条边,判断两点是否已经联通(kruskal 部分)如果联通,就在两点路径间寻找最大的b, 和这条边的b值相比较,如果更大一些,就切断u,v之间的路径, 并连上这条边;
如果不联通,就让它联通(好随意啊= =
最后寻找路径之间最大的b + 当前的a,和原来的答案相比较。
剩下的用lct维护
注意联通的方式是把把边看做点, 然后连接(所以加上n) ->link(u, i + n); link(v, i + n);
(由于我一直不理解怎么保证当前的a一定在路径上,所以这是自己yy的证明(可能有很大的bug,勿喷):当前的a如果不在(1,n)路径之中,但(1,n)已联通,那么最优值在之前已经被计算过,否则由于a是递增的,那么此时的a就是路径中最大的a)
下面是代码
1 /**************************************************************
2 Problem: 3669
3 User: cminus
4 Language: C++
5 Result: Accepted
6 Time:5104 ms
7 Memory:6128 kb
8 ****************************************************************/
9
10 #include <cstdio>
11 #include <algorithm>
12 using namespace std;
13 #define l(x) ch[x][0]
14 #define r(x) ch[x][1]
15 #define kd(x) (r(fa[x]) == x)
16 #define setc(f, c, k) (ch[fa[c] = f][k] = c)
17 #define isRoot(x) (r(fa[x]) != x && l(fa[x]) != x)
18 const int N = 150100;
19
20 struct Edge{
21 int u, v, a, b;
22 inline void init(){
23 scanf("%d %d %d %d", &u, &v, &a, &b);
24 }
25 inline bool operator <(const Edge &rhs)const{
26 return a < rhs.a;
27 }
28 }e[100100];
29 int fa[N], ch[N][2], rev[N], val[N], maxp[N], f[50100];
30 int INF = 0x7f7f7f7f;
31
32 inline void update(int x) {
33 maxp[x] = x;
34 if (val[maxp[x]] < val[maxp[l(x)]]) maxp[x] = maxp[l(x)];
35 if (val[maxp[x]] < val[maxp[r(x)]]) maxp[x] = maxp[r(x)];
36 }
37
38 inline void push(int x) {
39 if (rev[x] and x){
40 rev[x] = 0;
41 if (l(x)) rev[l(x)] ^= 1, swap(l(l(x)), r(l(x)));
42 if (r(x)) rev[r(x)] ^= 1, swap(l(r(x)), r(r(x)));
43 }
44 }
45
46 inline void pushDown(int x) {
47 if (! isRoot(x)) pushDown(fa[x]);
48 push(x);
49 }
50
51 inline void rotate(int x) {
52 int y = fa[x], t = kd(x);
53 setc(y, ch[x][t^1], t);
54 if (isRoot(y)) fa[x] = fa[y];
55 else setc(fa[y], x, kd(y));
56 setc(x, y, t^1);
57 update(y); update(x);
58 }
59
60 inline void splay(int x){
61 pushDown(x);
62 while(! isRoot(x)){
63 if (! isRoot(fa[x]))
64 if (kd(x) == kd(fa[x])) rotate(fa[x]);
65 else rotate(x); rotate(x);
66 }
67 }
68
69 inline void access(int x){
70 int t = 0;
71 while(x) {
72 splay(x);
73 r(x) = t; update(x);
74 t = x; x = fa[x];
75 }
76 }
77
78 inline void makeRoot(int x){
79 access(x); splay(x);
80 rev[x] ^= 1; swap(l(x), r(x));
81 }
82
83 inline void link(int u, int v) { makeRoot(u); fa[u] = v; }
84
85 inline void cut(int u, int v){
86 makeRoot(u);
87 access(v); splay(v);
88 fa[u] = l(v) = 0;
89 }
90
91 inline int query(int u, int v){
92 makeRoot(u);
93 access(v); splay(v);
94 return maxp[v];
95 }
96
97 int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
98
99 int main(){
100 int n, m;
101 scanf("%d %d", &n, &m);
102 int ans = INF;
103 for (int i = 1; i <= m; i++) e[i].init();
104 for (int i = 1; i <= n; i++) f[i] = i;
105 sort(e + 1, e + m + 1);
106 for (int i = 1; i <= m; i++){
107 int u = e[i].u, v = e[i].v, rt1 = find(u), rt2 = find(v);
108 val[i + n] = e[i].b; maxp[i + n] = i + n;
109 if (rt1 == rt2){
110 int p = query(u, v);
111 if (val[p] > e[i].b) cut(u, p), cut(v, p);
112 else continue;
113 }
114 else f[rt1] = rt2;
115 link(u, i + n); link(v, i + n);
116 if (find(1) == find(n)) ans = min(ans, val[query(1, n)] + e[i].a);
117 }
118 printf("%d\n", ans == INF ? -1 : ans);
119 return 0;
120 }
转载于:https://www.cnblogs.com/cminus/p/7056303.html