本文从WordPress迁移而来, 查看全部WordPress迁移文章
二分图 最小路径覆盖变形
题意:给一个DAG,用最少的路径覆盖所有的点,但是这里,路径中允许有重叠部分
因为路径中允许有重复的部分,用Floyd预处理出传递闭包,这样做的原因是,原本的最小路径覆盖不能有重复覆盖,实际上对于一些路径来说,是一种阻隔作用,现在可以穿过去,实际上是将原本的2条路径可以合为一条。Floyd处理后可以得到所有的连通性
1 |
|
Never or now.
本文从WordPress迁移而来, 查看全部WordPress迁移文章
二分图 最小路径覆盖变形
题意:给一个DAG,用最少的路径覆盖所有的点,但是这里,路径中允许有重叠部分
因为路径中允许有重复的部分,用Floyd预处理出传递闭包,这样做的原因是,原本的最小路径覆盖不能有重复覆盖,实际上对于一些路径来说,是一种阻隔作用,现在可以穿过去,实际上是将原本的2条路径可以合为一条。Floyd处理后可以得到所有的连通性
1 | #include <iostream> |