Description
给定你一个图,要求将其划分成两个点集,使得两个子集都是完全图,且使得属于两个完全图的边数最少,无重边自环
Solution
对完全图,考虑它的补图。把它的补图建出来后,一条边相连的两条边显然不能在一个点集中,因为总共两个点集,所以它的补图显然是二分图,根据二分图染色来判无解
由于补图不连通,对于每一个联通块的二分图,同一种颜色的只能放在同一点集里,而不同的联通块则没有要求
这个直接用bitset维护即可,表示点数为的点集是否存在,对于每个联通块,分别表示该联通块两种颜色个数
贪心地使两个点集的个数接近即可,即从从大到小贪心取
Code
1 |
|