洛谷 P1967 货车运输 树上倍增解LCA+并查集+生成树

缘起

此题较为综合, 是道好题~ 洛谷 P1967 货车运输

分析

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
题目描述
A国有n座城市，编号从 1到n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 q辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

输入格式
第一行有两个用一个空格隔开的整数n,m，表示 A 国有n 座城市和 m 条道路。

接下来 m行每行3个整数 x, y, z，每两个整数之间用一个空格隔开，表示从 x号城市到y号城市有一条限重为 z 的道路。注意：x 不等于 y，两座城市之间可能有多条道路 。

接下来一行有一个整数 q，表示有 q 辆货车需要运货。

接下来 q 行，每行两个整数 x、y，之间用一个空格隔开，表示一辆货车需要从 x 城市运输货物到 y 城市，注意： x 不等于 y 。

输出格式
共有 q 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货车不能到达目的地，输出-1。

输入输出样例
输入 #1复制
4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3
输出 #1复制
3
-1
3
说明/提示
对于30%的数据，0 < n < 1,000,0 < m < 10,000,0 < q< 1,000

对于60%的数据，0 < n < 1,000,0 < m < 50,000,0 < q< 1,000；

对于100%的数据，0 < n < 10,000,0 < m < 50,000,0 < q< 30,000

时间限制
1s
内存限制
125MB

做这道题目的目的是因为可以学习新的算法——LCA树上倍增解法.

先不扯lca. 首先来看看本题的思路——首先题目要求的是q个询问——每次询问的是两个点之间的所有通路的最小权中的最大值。

首先, 使用kruskal求出最大生成树（因为原图未必连通, 所以其实是最大生成森林）. 然后任何两点，用并查集就知道他俩在不在一棵生成树上. 如果不在, 直接输出-1， 如果在的话，求出他俩在这棵最大生成树上的lca. 并且求出它俩到lca的最小权边，两者再取小就是答案.

下面介绍一下如何使用树上倍增求解LCA问题，这是一种在线算法，而不是tarjan这种离线算法.

关于树上倍增解LCA问题我是参考的【1】，虽然那里的讲解还是有一点问题（我在他的文章下面留言了）.

但是总体讲解的还是清晰的.

首先树上倍增求解LCA的复杂度是 O(nlogn+qlogn)的, 其中 nlogn 是构建fa数组的复杂度. 而这个fa数据结构每次回答询问的复杂度是 O(logn). 所以回答q个询问的复杂度是 qlogn

首先，什么是LCA就不必我多说了吧~ 不懂的童鞋参见【2】. 然后请参考一下【3】，这是一道经典的阿里面试题，树上倍增求LCA的思想源于它.

其实就是两根链表如果相交的话, 首先比较他们的长度, 然后让长的链表先走. 走到这两根链表等长的时候, 就可以齐步走了, 如果有公共节点的话, 则一定碰到. 而且一旦碰到, 返回的就是lca.

一图胜千言

即q先从C开始走, 走到B位置, 即此时，B到E的长度=A到E的长度. 然后此时p才从A出发,q才从B出发, 齐步走(一格一格的走), 则一定能在LCA碰到. 这是LCA最暴力的解法. 回答一次询问的复杂度是O(n)的. 如果仅仅是一次询问的话(譬如这道面试题), 不需要使用树上倍增，因为树上倍增初始化fa的复杂度都已经是nlogn了的. 但是对于本题这种回答多个询问的，使用树上倍增求解LCA是极为有必要的. 因为一旦使用树上倍增，则只需预处理一次, 然后后面对于每次询问只需花费 logn的时间就能回答了.

暴力算法的另一种版本是预处理出A到根节点的所有节点, 然后让C出发, 能走到第一个节点就是他俩的LCA. 当然，回答LCA的复杂度依旧是On的——慢的一笔~

那么怎么改进暴力算法呢? 或者说暴力算法慢在哪里呢? 慢就慢在它是一格一格的走的. 所以才慢. 如果让它能每次跳2^i格, 快速的略去前面不可能是LCA的格子的话, 则暴力算法的速度就被杠杠的加速了.

wait wait wait~ 跳 2^i 步? 如果i大了的话, 则可能跳到LCA的祖先去了，就像上图, 直接跳到E去了, i如果小了的话，可能就还没到LCA（例如仅仅到了A1和B1，还没到LCA）。其实不要紧的, 我们完全可以调整嘛~ 怎么说, 一旦跳的步数大了(例如，干到了F), 我们就下调i–, 直至他们不相等了（即到了A1和B1，A1!=B1）, 则将A更新为A1, 将B更新为B1，但是注意, 此时A1和B1未必恰好是LCA前一个点！！！ 所以这个时候，不能暂停i的遍历（i要继续i–）, 要继续考察A1和B1的2^i祖先. 因为此时i已经比较小了，则其实此时就进入了微调阶段. 当然，对于当前i, A1的2^i祖先和B1的2^i祖先依旧可能相同, 即又跑到[LCA, E]中去了. 但是i还会继续减小, 注意，一旦A1和B1的2^i祖先跑到 [LCA, E]这个区间去了, 则A1和B1是不会更新的. 一旦i小到使得A1, B1的2^i祖先不相等的时候, 譬如A1的2^i祖先是A2, B1的2^i祖先是B2, 且 A2!=B2, 则A1更新为A2，B1更新为B2. 但是A2、B2比A1、B1更加接近LCA！然后i依旧继续递减（即for循环不停止），A2、B2的2^i祖先可能又跑到[LCA, E]去了，则A2、B2不变，继续等i变小, 使得A2的祖先A3和B2的祖先B3不相等了,…. 直至到i变成0了——即直接父节点.

四不四树上倍增有一种来来回回上上下下的赶脚?

也就是说——树上倍增求LCA的算法本质上就是 大步流星（即跳2^i）逼近+微调（即减小i）的算法.

树上倍增是一款优秀的O(logn)的在线LCA算法.

那么回到本题, 本题该怎么做呢? 思路就是首先使用 kruskal（自然，讲到kruskal的话，自然是需要配合并查集的）求出最大生成树. 期间将最大生成森林维护出来（即通过链式前向星构有向图. 即一边为两弧）. 然后nlogn时间维护出fa[i][j] 数组, 其中 fa[i][j] 的含义是顶点i的第2^j个祖先是谁. 然后对于每个询问求出LCA, 那么怎么求出最终的答案呢? 自然是前面说的——询问涉及的两个点到LCA的最小边权的较小者.

而且借助本题, 我将学习一个新的算法——快读快写模板. 即对于题目有大量读写导致超时情况, 可以使用一个精巧的快读快写模板. 来源于【4】, 它比stdio库的scanf还要快. 一般能快40ms左右~

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
140
141
142
143
144
145
146
147
148
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
//#define LOCAL
const int maxn = 10005, maxm = 50005, inf = 0x3f3f3f3f;
int n,m,q, f[maxn], fa[maxn][21], cnt, head[maxn], len[maxn][21], dep[maxn]; // f是并查集数组, fa[i][j]是i的第2^j个祖先, len[i][j]是i到它的第2^j个祖先的最小边权, dep[i]是顶点i在其所在的最大生成树中的深度(根节点的深度规定为1),这里fa、len的第一维到达了21, 尽管2^14=16384已经大于maxn了, 但是为了来来回回上上下下的充分, 我们从2^20开始
bool v[maxn];

struct Edge
{
	int x,y,len;
	bool operator <(Edge &o)
	{
		return len>o.len;
	}
}edges[maxm];

struct Arc
{
	int from,to,nxt,len;
}g[maxm<<1];

void addArc(int from, int to, int len)
{
	g[cnt].from = from, g[cnt].to = to, g[cnt].len = len, g[cnt].nxt = head[from];
	head[from] = cnt++;
}

int getf(int i)
{
	return f[i]<0?i:f[i]=getf(f[i]);
}

void merge(int i, int j) // 注意, 调用此函数的时候, i和j都是根节点, 所以f[i]和f[j]都<0
{
	f[i]<f[j]?f[j]=i:f[i]=j;
}

void kruskal()
{
	sort(edges, edges+m);
	for (int i = 0; i<m; i++)
	{
		int fx = getf(edges[i].x);
		int fy = getf(edges[i].y);
		if (fx!=fy)
		{
			addArc(edges[i].x, edges[i].y, edges[i].len);
			addArc(edges[i].y, edges[i].x, edges[i].len);
			merge(fx, fy);
		}
	}
}

void dfs(int i)
{
	v[i] = true;
	for (int h = head[i],to; ~h; h = g[h].nxt)
	{
		to = g[h].to;
		if (!v[to])
		{
			fa[to][0] = i;
			len[to][0] = g[h].len;
			dep[to] = dep[i]+1;
			dfs(to);
		}
	}
}

int lca(int x, int y) // 树上倍增解LCA(x,y)问题
{
	int ans = inf;
	int fx = getf(x), fy = getf(y);
	if (fx!=fy)
	{
		return -1;
	} // 不在一个最大生成树中, 自然不可达
	if (dep[x]>dep[y])
	{
		swap(x,y);
	} // 保证y的深度>=x, 即保证y是图中的C点, x是上图中的A点
	for (int i = 20; ~i; i--)
	{
		if (dep[fa[y][i]]>=dep[x]) // 则i已经小到让fa的第2^i个祖先深度>=x的深度了, 则更新一下y, 这意味着至多到达LCA~ 所以要维护一下ans答案
		{
			ans = min(ans, len[y][i]);
			y = fa[y][i];
		}
	} // 让y和x处于同一深度, 就像上图那样, 要保证C来到了B点然后再和A齐步走, 其实这也是大步流星+微调
	if (x==y)
	{
		return ans;
	} // 如果高度一致的时候就是同一个点的话, 则得到答案了
	for (int j = 20; ~j; j--)
	{
		if (fa[x][j]!=fa[y][j]) // 这意味着还没到LCA呢~ 所以要维护一下答案
		{
			ans = min(ans, len[x][j]), ans = min(ans, len[y][j]);
			x = fa[x][j], y = fa[y][j];
		} // 注意, 不能break. 因为这是在不断的微调
	} // 最后x和y距离lca(x,y)都只差一步之遥
	ans = min(ans, len[x][0]), ans = min(ans, len[y][0]); // 因为x和y都距离lca(x,y)一步之遥了, 所以要把最后一段len[x][0]、len[y][0]给min上
	return ans;
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d%d", &n,&m);
	memset(f, -1, sizeof(f));
	memset(head, -1, sizeof(head));
	for (int i =0; i<m; i++)
	{
		scanf("%d%d%d", &edges[i].x, &edges[i].y, &edges[i].len);
	}
	kruskal(); // 生成最大生成森林
	for (int i = 1; i<=n; i++)
	{
		if (!v[i]) // 则i是最大生成森林中的某一棵最大生成树的根节点
		{
			len[i][0] = inf; // 根节点的父节点当然不存在啦~ 所以我们赋它为0,而它到0的最小边权是inf
			fa[i][0] = 0;
			dep[i] = 1; // 根节点在最大生成树中的深度自然是1(当然,赋值成0也没关系, 只是习惯问题)
			dfs(i);
		}
	} // 初始化fa和len
	for (int j=1;j<=20; j++) // j一旦比较大,没关系的,都是0 了
	{
		for (int i = 1; i<=n; i++)
		{
			fa[i][j] = fa[fa[i][j-1]][j-1];
			len[i][j] = min(len[i][j-1], len[fa[i][j-1]][j-1]); // len[i][j]分成i到它的第2^{j-1}个祖先以及i的第2^{j-1}个祖先到i的第2^j个祖先两段路程, 取小即可
		}
	} // nlogn初始化lca
	scanf("%d", &q);
	while(q--)
	{
		int x,y;
		scanf("%d%d", &x, &y);
		printf("%d\n", lca(x,y));
	}
	return 0;
}

ac情况

1
2
3
4
5
6
所属题目
P1967 货车运输
评测状态
Accepted
评测分数
100

注意，上面的代码是没有使用快读快写模板的. 如果我们使用快读快写模板的话

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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <ctype.h>
using namespace std;
//#define LOCAL
const int maxn = 10005, maxm = 50005, inf = 0x3f3f3f3f;
int n,m,q, f[maxn], fa[maxn][21], cnt, head[maxn], len[maxn][21], dep[maxn];
bool v[maxn];

template <typename T>
void read(T &x) // 快读模板, 读入x
{
	x = 0;
	int f =1; // 符号
	char c = getchar();
	while(!isdigit(c))
	{
		if (c=='-') 
		{
			f = -1; // 说明是负数
		}
		c = getchar(); // 也能吸收多余的换行符、空格啥的, 所以这块快读板子很强大的.
	}
	while(isdigit(c))
	{
		x = (x<<3)+(x<<1)+(c^48); // 洪特规则, c^48, 48 就是'0', 所以 c^48 其实就是c-48
		c = getchar();
	}
	x*=f;
} // 之所以比scanf快的原因在于处理单个字符（8位）

void write(int x) // 快写模板
{
	if (x<0)
	{
		putchar('-');
		x = -x;
	} // 处理符号位
	if (x>9)
	{
		write(x/10);
	}
	putchar(x%10+'0');
}

struct Edge
{
	int x,y,len;
	bool operator <(Edge &o)
	{
		return len>o.len;
	}
}edges[maxm];

struct Arc
{
	int from,to,nxt,len;
}g[maxm<<1];

void addArc(int from, int to, int len)
{
	g[cnt].from = from, g[cnt].to = to, g[cnt].len = len, g[cnt].nxt = head[from];
	head[from] = cnt++;
}

int getf(int i)
{
	return f[i]<0?i:f[i]=getf(f[i]);
}

void merge(int i, int j)
{
	f[i]<f[j]?f[j]=i:f[i]=j;
}

void kruskal()
{
	sort(edges, edges+m);
	for (int i = 0; i<m; i++)
	{
		int fx = getf(edges[i].x);
		int fy = getf(edges[i].y);
		if (fx!=fy)
		{
			addArc(edges[i].x, edges[i].y, edges[i].len);
			addArc(edges[i].y, edges[i].x, edges[i].len);
			merge(fx, fy);
		}
	}
}

void dfs(int i)
{
	v[i] = true;
	for (int h = head[i],to; ~h; h = g[h].nxt)
	{
		to = g[h].to;
		if (!v[to])
		{
			fa[to][0] = i;
			len[to][0] = g[h].len;
			dep[to] = dep[i]+1;
			dfs(to);
		}
	}
}

int lca(int x, int y)
{
	int ans = inf;
	int fx = getf(x), fy = getf(y);
	if (fx!=fy)
	{
		return -1;
	} 
	if (dep[x]>dep[y])
	{
		swap(x,y);
	}
	for (int i = 20; ~i; i--)
	{
		if (dep[fa[y][i]]>=dep[x])
		{
			ans = min(ans, len[y][i]);
			y = fa[y][i];
		}
	} 
	if (x==y)
	{
		return ans;
	} 
	for (int j = 20; ~j; j--)
	{
		if (fa[x][j]!=fa[y][j])
		{
			ans = min(ans, len[x][j]), ans = min(ans, len[y][j]);
			x = fa[x][j], y = fa[y][j];
		}
	} 
	ans = min(ans, len[x][0]), ans = min(ans, len[y][0]);
	return ans;
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	read(n), read(m); // 使用快读模板读取数据
	memset(f, -1, sizeof(f));
	memset(head, -1, sizeof(head));
	for (int i =0; i<m; i++)
	{
		read(edges[i].x);
		read(edges[i].y);
		read(edges[i].len);
	}
	kruskal();
	for (int i = 1; i<=n; i++)
	{
		if (!v[i]) 
		{
			len[i][0] = inf; 
			fa[i][0] = 0;
			dep[i] = 1; 
			dfs(i);
		}
	} 
	for (int j=1;j<=20; j++) 
	{
		for (int i = 1; i<=n; i++)
		{
			fa[i][j] = fa[fa[i][j-1]][j-1];
			len[i][j] = min(len[i][j-1], len[fa[i][j-1]][j-1]); 
		}
	}
	read(q);
	while(q--)
	{
		int x,y;
		read(x), read(y);
		write(lca(x,y)); // 使用快写模板写出数据
		puts("");
	}
	return 0;
}

ac情况

1
2
3
4
所属题目
P1967 货车运输
评测状态
Accepted

经过洛谷oj的评测, 第一版没有使用快读快写的代码最慢的那个点耗时48ms, 而该点使用了快读快写的模板耗时32ms. 所以快读快写模板的确可以提高代码的性能. 我收下了~ 不过

快读快写板子对于一般的题目用不着~ 比赛的时候也不会去写. 只是用来刷榜装逼用的.

参考

【1】https://blog.csdn.net/weixin_39872717/article/details/81186358

【2】https://yfsyfs.github.io/2019/07/15/LCA/

【3】https://yfsyfs.github.io/2019/08/12/%E5%89%91%E6%8C%87offer-%E6%89%BE%E4%B8%A4%E6%A0%B9%E9%93%BE%E8%A1%A8%E7%9A%84%E7%AC%AC%E4%B8%80%E4%B8%AA%E5%85%AC%E5%85%B1%E8%8A%82%E7%82%B9/

【4】https://www.cnblogs.com/TY02/p/10606685.html