二分图

看来脑瓜子还是不够灵活啊。以前看到“matching”、“bipartite”一类的标签,试图二分图时只晓得将题目中同一类的元素转化为点,将相对关系转化为边。但实际上,二分图也可以表示其他的二元逻辑关系,例如包含、排除。

例如[NOIP2010 提高组] 关押罪犯,一个经典做法是将罪犯转化为点集,将冲突关系符合一定条件的相互连边,然后二分答案作二分图匹配。(扩展域并查集实质上也是在贪心的基础上,运用“二分图匹配”的思想检查方案合法性……对吧?)

再例如AtCoder ABC 228 G – Digits on Grid,计数DP的转移也是在行、列元素分别作为左部、右部,以方格中的元素作为边权的二分图上进行的。

这道题则非常精妙——CF1634E – Fair Share。看到“要将所有元素分成两个相等的可重集”时,我认为应当用可重集作为二分图的左部和右部。但是这样一来,如何进行匹配呢?正解则是将数组ii包含元素aia_i逻辑关系转化为边——左部为各个数组,右部为相同的元素。可以发现,能够有解的充分必要条件是“每个元素均统共出现了偶数次”,同时“每个数组含有偶数个元素”,那么该图中每个节点的度数均为偶。记得小学奥数的一笔画问题么?它有一个更专业的术语,曰欧拉回路。事实上,一张无向图存在欧拉回路,当且仅当不存在度数为奇的节点。所以,我们直接求解一条欧拉回路,将从左部到右部遍历的边记作LL,从右部到左部遍历的边记作RR就是一个正确的解。

More
  • 2022年2月7日