NCPC 2014 Amanda Lounges 二分图染色

给一个图,有些边需要两端均为1,有些边两端均为0,有些边两端需要只有一个为1,问能不能实现,最少填多少个1.

对于两端都是1,和两端都是0的,我们暴力填上去,并且把相连的其他两端不同的顺上去。现在我们剩一些联通分量,边均为两端要求不同。我们对于每个联通分量任取一点,先后尝试填0,1,取最小值即可。

发表评论