http://uoj.ac/problem/3

题意：一个无向图，要从1到n，每条边有两个权值a,b，最终的花费a值，b值不能小于路径上的边权值，求最终最小a，b值之和。

有二维，肯定是要把一维排序，另一维求最小，最后再比较答案。

有两种做法。

做法一：分层图SPFA

把边按照a值从小到大排序，再逐个插到图里，每次都求从1到n的最大b值最小的路径，由于新增了边，所以要再把新增的边加进SPFA的队列里，让它继续跑，不要重新建图。有点类似分层图网络流。最后比较新的b值加a值是否更小，由于如果路径不走新边的话，就和上次答案一样，已经存下来了，所以只需要假设路径走新边即可。

然而这种做法被新加的数据卡了。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e6 + 10;
int n, m;
struct E
{
	int u, v, a, b;
	bool operator<(const E& t)const {
		return a < t.a;
	}
};
vector<E>edges;
struct EE
{
	int v, b;
};
vector<EE>G[maxn];
int d[maxn], inq[maxn];
queue<int>que;
void spfa() {
	while (!que.empty()) {
		int u = que.front();
		que.pop(); inq[u] = 0;
		for (int i = 0; i < (int)G[u].size(); i++) {
			EE e = G[u][i];
			int nb = max(d[u], e.b);
			if (d[e.v] > nb) {
				d[e.v] = nb;
				if (!inq[e.v])
					que.push(e.v), inq[e.v] = 1;
			}
		}
	}
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int u, v, a, b;
		scanf("%d%d%d%d", &u, &v, &a, &b);
		edges.push_back(E{ u,v,a,b });
	}
	int ans = INF;
	sort(edges.begin(), edges.end());
	memset(d, 0x3f, sizeof(d));
	que.push(1);
	d[1] = 0;
	for (int i = 0; i < (int)edges.size(); i++) {
		E e = edges[i];
		G[e.u].push_back(EE{ e.v,e.b });
		G[e.v].push_back(EE{ e.u,e.b });
		que.push(e.u); inq[e.u] = 1;
		que.push(e.v); inq[e.v] = 1;
		spfa();
		ans = min(ans, d[n] + e.a);
	}
	if (ans < INF)cout << ans << endl;
	else cout << -1 << endl;
	return 0;
}

 

做法二：LCT

最小生成树一定是最小瓶颈生成树。任意两点间最大权值一定最小。

但是没法直接维护生成树，因为加进一条边后并不知道是否要而更新1到n的路径。

所以动态维护生成树以及生成树上1到n的路径上的最大权值。

动态树用LCT维护。复杂度 O(nlog⁡n+mlog⁡n)O(n \log n + m \log n)

但是LCT没有边权，所以把边权转成点权，原来的点在LCT上仍为点，点权为0，不影响答案，原来的边在LCT里变成点，点权为原边权，每次加边时边变成的点要link原来的两个点。

同样按照a值从小到大插入，并查集维护有环时判断如果a+b值更小，就要cut原来的1到n路径上的最大b值边，换成新边。由于每次a值都是新加的边的a值，所以只要看b值，而b值一定是不断变小的，所以换边不会有错。

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
138
139
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 10;
struct LCT
{
	#define lc c[x][0]
	#define rc c[x][1]
	int v[maxn], f[maxn], c[maxn][2], siz[maxn], mx[maxn];
	bool r[maxn];//区间翻转
	inline bool nroot(int x) {
		return c[f[x]][0] == x || c[f[x]][1] == x;
	}
	inline void pushup(int x) {
		mx[x] = x;
		if (lc&&v[mx[lc]] > v[mx[x]])mx[x] = mx[lc];
		if (rc&&v[mx[rc]] > v[mx[x]])mx[x] = mx[rc];
	}
	inline void rev(int x) { swap(lc, rc); r[x] ^= 1; }
	inline void pushdown(int x) {
		if (r[x]) {
			if (lc)rev(lc);
			if (rc)rev(rc);
			r[x] = 0;
		}
	}
	inline void update(int x) {
		siz[x] = siz[lc] + siz[rc];
	}
	inline void rotate(int x) {
		int y = f[x], z = f[y], k = c[y][1] == x, w = c[x][k ^ 1];
		if (nroot(y))c[z][c[z][1] == y] = x;
		if (w)f[w] = y;
		c[x][k ^ 1] = y; c[y][k] = w;
		f[y] = x; f[x] = z;
		pushup(y);
		update(y), update(x);//先更新y
	}
	inline void pushall(int x) {
		if (nroot(x))pushall(f[x]);
		pushdown(x);
	}
	inline void splay(int x) {
		pushall(x);
		int y, z;
		while (nroot(x)) {
			y = f[x]; z = f[y];
			if (nroot(y))rotate((c[y][0] == x && c[z][0] == y ? y : x));
			rotate(x);
		}
		pushup(x);
	}
	inline void access(int x) {
		for (int y = 0; x; y = x, x = f[x])
			splay(x), rc = y, pushup(x);
	}
	inline void makeroot(int x) {
		access(x); splay(x);
		rev(x);
	}
	int findroot(int x) {
		access(x); splay(x);
		while (lc)pushdown(x), x = lc;
		splay(x);
		return x;
	}
	inline void split(int x, int y) {
		makeroot(x);
		access(y); splay(y);
	}
	inline void link(int x, int y) {
		makeroot(x);
		if (findroot(y) != x)f[x] = y;
	}
	inline void cut(int x, int y) {
		makeroot(x);
		if (findroot(y) == x && f[y] == x && !c[y][0]) {
			f[y] = c[x][1] = 0;
			pushup(x);
		}
	}
	int query(int x, int y) {
		makeroot(x); access(y); splay(y);
		return mx[y];
	}
}lct;
int n, m;
int p[maxn], rk[maxn];
int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
void merge(int x, int y) {
	x = find(x), y = find(y);
	if (x == y)return;
	if (rk[x] < rk[y])p[x] = y;
	else {
		p[y] = x;
		if (rk[x] == rk[y])rk[x]++;
	}
}
struct E
{
	int u, v, a, b;
	bool operator<(const E& t)const {
		return a < t.a;
	}
}es[maxn];
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)p[i] = i;
	for (int i = 1; i <= m; i++) {
		int u, v, a, b;
		scanf("%d%d%d%d", &es[i].u, &es[i].v, &es[i].a, &es[i].b);
	}
	sort(es + 1, es + m + 1);
	int ans = INF;
	for (int i = 1; i <= m; i++) {
		int u = es[i].u, v = es[i].v, a = es[i].a, b = es[i].b;
		if (find(u) == find(v)) {
			int t = lct.query(u, v);
			if (lct.v[t] > b) {
				lct.cut(t, es[t - n].u);
				lct.cut(t, es[t - n].v);
			}
			else {
				if (find(1) == find(n))ans = min(ans, a + lct.v[lct.query(1, n)]);
				continue;
			}
		}
		else {
			merge(u, v);
		}
		lct.v[i + n] = b; lct.mx[i + n] = i + n;
		lct.link(u, i + n); lct.link(v, i + n);
		if (find(1) == find(n))ans = min(ans, a + lct.v[lct.query(1, n)]);
	}
	if (ans == INF)puts("-1");
	else printf("%d\n", ans);
	return 0;
}