【BZOJ2756】【SCOI2012】奇怪的游戏

又一道不会做的网络流

首先把格子黑白染色,那么每次操作一定是给某个黑格子和某个白格子同时\(+1\)

记黑白格子本来的和为\(s1,s2\)

如果\(n,m\)全为奇数,那么某种颜色会多一个(假设为黑色),最后所有格子的数值一定是\(s1-s2\)

如果\(n,m\)不全为奇数,那么黑白格子的个数是相同的,则必要开始时\(s1=s2\),最后所有格子的值可能的取值是大于等于某个数(因为可以每次再铺一层),所以二分答案

检验能不能所有格子同时达到某个值用网络流即可,黑白格子分两边,相邻的点连边,每个点到源/汇点边权为它还差多少次操作

说点什么

  Subscribe  
提醒