hdu 5285 wyh2000 and pupil (交叉染色法,二分图点集差最大)

题目链接:hdu 5285 题目lianjie

题意:给定n个小朋友,以及小朋友之间的关系,要求将小朋友分成两组,并且每组至少一个人,现在问能否这样分组,如果有解,输出两组的人数,并保证第一组的人数尽可能地大。

思路:。。。一开始看到n的数据范围。。。想当然的以为会给认识的人的关系。。。尼玛。。。求个补图就够受的了。。。。不会做,卒。

结果发现。。竟然给的是两个人不认识的关系。。。2333

那么我们来交叉染色。。。

实际上交叉染色的过程中,颜色相同的点属于二分图中相同的点集合。

交叉染色其实是在模拟交错轨的过程…?

由于图不一定联通,可能由多个联通块。

我们在交叉染色的时候记录一下0,1的个数(也就是两个点集的大小)

然后每次把大的累加(因为没说不认识的就是默认认识了。。。)

无解的情况有:任何一个联通快无解或者n<=1

此外还需要注意,m可能为0.

特判一下,m为0或者为1,直接输出n-1和1.

以及!

n<=1的无解是在特判m之前的。。。。我好傻啊。

n<=1的无解是在特判m之前的。。。。我好傻啊。

n<=1的无解是在特判m之前的。。。。我好傻啊。

 

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz