萌新想了一下午也不知道这题建图的正确性证明
查看原帖
萌新想了一下午也不知道这题建图的正确性证明
113546
ix35Eschaton楼主2021/5/6 15:47

这道题将每个 (x,y)(x,y) 连成串联的 RR 条边,并且对于相邻格子进行了差分限制。

显然,一组合法的 f(x,y)f(x,y) 对应了一组合法的割,但是如何证明任意一组割都对应了至少一个合法的 f(x,y)f(x,y),或者说不小于一组合法的 f(x,y)f(x,y)?为何不存在一条串联链上割掉了两条边的“作弊”情况?

萌新想了一下午也没想出来,hack 了一下午也没 hack 出来,所以发帖求教。

2021/5/6 15:47
加载中...