louhc

题解

未归档(78)

/ 注册

全部文章 / 题解（共2篇）

题解 | 算法竞赛进阶指南 K取方格数

思路费用流裸题.将每个点拆成入点和出点,入点与出点之间连边,容量为1,价值为该点的数.这样该点只能经过一次且经过会得到该数的代价.实际上每个格子能经过多次,但只能得到一次的代价,因此再连一条容量为,价值为0的边.然后源点向连边,向汇点连边,跑一遍最大费用最大流即可. 代码 #include<...

费用流 Floyd

2019-08-24

0 573

题解 | 算法竞赛进阶指南 Vani和cl2捉迷藏

思路事实上,此题等价于求最小路径可重覆盖.为什么呢?我们可以考虑构造出所有的藏身点.首先,跑一遍最小路径可重覆盖后,将所有路径的终点加入集合.假设表示.表示传递闭包后的边集.如果,选取,不断沿着路径向前移,直到为止.不断重复以上过程,直到停止.容易证明,这样肯定能找到一个合法的方案.这题不需要输出...

Floyd 最小路径覆盖

2019-08-24

0 645