January 12, 2022
用 [SDOI2011]染色 的代码稍微改改即可。
图论题，算法都不难，但是要拼的东西很多，比较考验底力。。。暴力 Floyd 可以拿 20 分。。
正解先 scc()，然后题目的条件告诉我们可以用树来代替 scc() 后的 dag 去表示可达关系，
k=0 的情况，直接在树上用前缀和减减即可，然后 这个题解 告诉我们可以使用虚树来避免讨论 k。。
我们用 atl 里提供的 scc()，
再从 这个题里找来 lca，（用倍增祖先我会 TLE。。）
再从 这个题里找来虚树，
最后缝合在一起，暴力 bfs() 即可，（Floyd 的话貌似要开路径数和权值和两个数组。）
btw，无论 Kosaraju、还是 Tarjan，都是基于 dfs() 的算法，强连通缩点完成之后的结构，都是满足逆向拓扑序的，取反后，直接把 1 号节点作为根节点即可，可以省一个拓扑排序。。。
– https://stackoverflow.com/questions/32750511/does-tarjans-scc-algorithm-give-a-topological-sort-of-the-scc
Posted by
xiaodao
Category: 日常
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。