louhc

分类

未归档(78) 题解(81)

/ 注册

全部文章（共2篇）

题解 | 算法竞赛进阶指南 Cable TV Network

思路这是一个无源无汇的最小割问题.或者说叫"无向图全局最小割".一个很暴力的思想就是枚举任意两个点作为源点和汇点.复杂度大概是,但是由于跑不到上界,还是可以过的.如果对这个复杂度不满意,可以枚举源点,其他点向汇点连边,复杂度为,优秀得多.你还可以使用二进制思想,枚举每一位,将所有点分成两部分,源点...

最小割

2019-08-24

0 553

题解 | 算法竞赛进阶指南骑士放置

思路很明显,一对相斥的位置,横纵坐标之和的奇偶性肯定不同.所以可以构成一个二分图.源点向所有横纵坐标之和为奇数的点连边,为偶数的向汇点连边,边权都为1.一对相斥的点之间连边,跑一遍最小割即可.或者如果你懒得写网络流,你可以套用最大独立点集的模型,跑匈牙利即可.虽然效率比网络流低得多. 代码 #in...

最大独立点集网络流最小割

2019-08-24

2 528