原文作者:莉墨 lymoe
官方题解所有者:我
所以文章中的一些第一人称指的是 lymoe 不是我 qwq
另外在此说明了版权问题
题目灵感
当初其实是想考察一下 “树上全源最短路” 和 “二分图染色”,想了很久也没想出怎么出。
最后就把这两个算法合到一块,就出现了这个题。
原本这个题难度并不高(刚开始数据 n 最大为 1000(其实数据加强后,难度也不高 QAQ)),后来 WAAutoMaton 发现了一个 O(n) 的算法,于是这个题就稍微难了一点。
Part 0-题目分析
分析题目可以发现,我们可以建立一个新图,新图中的点和原图中的点一一对应。如果 dis(u,v)≥k 则在新图中把 u,v 相连。
那么新图中的任意一个 “环” 都对应一个满足题目条件的序列 a1,a2,a3,…,am 。
而如果新图中存在奇环,则为 “无解”。
part 1-测试点 1~10 40 分
先用弗洛伊德算法求出全源最短路,建立新图。
我们知道不存在奇环的图为二分图。所以对新图进行二分图染色(或者用并查集判断二分图),若该图是二分图,则 “有解”,若该图不是二分图,则 “无解”。
part 2-测试点 15~20 64 分(40+24)
把弗洛伊德算法改用 dfs 求树上全源最短路即可。如果你嫌码量太小,使用 tarjan、树剖、倍增等求 lca 的方法求最短路也可。
part 3-测试点 11~14 16 分
对于这一部分和下一部分的分数,已经不需要建立新图了,但是为了方便证明,我们还会说到这个新图。
我们来考虑一下这个退化成链的部分。
通过在纸上手造几个数据,我们可以发现新图的一个性质:若新图上存在奇数环,则一定存在三元环。
那么怎么证明呢?
由于链上的环跟链上的点编号无关,不妨设这个链上的点从左往右编号依次为 1,2,3,…,n 。(1,2之间连边,2,3 之间连边… 以此类推)
设这个链对应的新图存在奇环 a1,a2,…,am ,且 m≠3 。
不妨设 a1 为奇环中编号最小的点,ax 为奇环中编号最大的点。
那么显而易见 dis(a1,ax)≥k 。(因为如果奇环中距离最远的两个点距离都小于 k 的话,则新图上一定不存在这个奇环)
假设奇环上不存在一点 aq 满足 dis(a1,aq)≥k and dis(a1,ax)≥k ,则
∵dis(a1,a2)≥k
∴dis(a2,ax)<k
∵dis(a2,a3)≥k,dis(a2,ax)<k
dis(a3,ax)≥k,dis(a1,a3)<k
…
以此类推,可以用数学归纳法证明(这里就省略数学归纳的过程),dis(a2p,ax)<k ,dis(a2p+1,a1)<k ,其中 p∈N∗ 。那么可以发现,因为 dis(a2p,ax)<k ,所以无法构成包含 ax 的奇环。
故产生矛盾,则奇环上存在一点满足 dis(a1,aq)≥k and dis(a1,ax)≥k 。
则证明了存在奇数环就一定存在三元环。
那么接下来,我们可以猜测:若存在三元环,则存在包括 1 号点和 n 号点的三元环。
证明:
我们设三元环为 (a1,a2,a3) 且 a1<a2<a3 。
∵dis(a1,a2)≥k,a1≥1
∴dis(1,a2)≥k
∵dis(a2,a3)≥k,a3≤n
∴dis(a2,n)≥k
所以存在三元环 (1,a2,n) 满足条件 。
那么对于链的解法就显而易见了。我们只需要求一下前缀和,然后看看链上是否存在一点能与首尾构成三元环。
part 4-测试点 21~25 100 分
对于这部分分,我们可以采用类比法(类比 part 3)。
同理我们先来证明,若存在奇数环,则存在三元环。
首先我们找到奇环里距离最远的两个点 a1,ax 。
假设奇环上不存在一点 aq 满足 dis(a1,aq)≥k and dis(a1,ax)≥k ,则
∵dis(a1,a2)≥k
∴dis(a2,ax)<k
∵dis(a2,a3)≥k,dis(a2,ax)<k
∴dis(a3,ax)≥k,dis(a1,a3)<k
…(若比较难理解可以自行画图)
所以与 part 3 相同,因为 dis(a2p,ax)<k ,所以无法构成包含 ax 的奇环。
那么接下来,我们可以猜测:若存在三元环,则存在包括直径两个端点的三元环。
证明:
首先我们将树简化:
大写字母表示点,小写字母表示边,该简化图中边长可以为 0 。
AB 为树的直径, (D,F,G) 为直径外一三元环。
我们可以假设三元环上任意一点都不满足“到 A 的距离不小于 k 且到 B 的距离不小于 k ” 。
不妨设 (f+d)+l+b<k ,则
(f+d)+c≥k
∴b+l<c
∴a+l+c>a+l+b+l≥a+b
则 dis(A,D)>dis(A,B) ,则 (A,B) 不为直径,产生矛盾。
所以三元环上存在一点满足 “到 A 的距离不小于 k 且到 B 的距离不小于 k ”。
那么正解的算法也就显而易见了,只需要先求树的直径,再看看是否存在一点到直径两端距离不小于 k 。
最后贴出 std:
1 条评论
Vegetable Chicken · 2021年1月26日 8:52 下午
orzorz 书虫太强了