louhc

题解

未归档(78)

/ 注册

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

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

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

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

2019-08-24

2 528