P2175 小Z的游戏分队

题目描述

小Z受不了寂寞,准备举办一次DOTA比赛,为了能让ACM班全部都参加比赛,他还特制了一张DOTA地图能够支持任意多人打任意多人。 现在问题来了,怎么把这么多人分成两队?小Z的想法是,每个人报上自己愿意同队的同学,接着小Z会按如下要求将所有人分为两队: 对任意同学甲,和同学甲同队的人,必须都是同学甲愿意同队的同学。 小Z希望两队的人数差尽量小,如果这种分组不存在,那么输出No solution。


这道题应该是一个二分图染色+背包问题
考虑以不信任关系建图。
对于这样建的图,可以想到,如果存在这样的方案,那么建完的图完全符合二分图的性质。(同组内不互相连边,异组直间互相连边)
所以可以跑一遍二分图染色来判断有没有符合方案的分组。
补图会有若干个连通块,可以把每个连通块当做一个物品,它的权值就表示两种颜色之差。
就变成了一个01背包问题

 

分类: 题解

说点什么

avatar
  Subscribe  
提醒