2016 ICPC 大连 区域赛 A Wrestling Match (交叉染色法判断二分图)

题意:

给出n个点m条边,以及已知的好点和坏点。一个边连接的2个点一定是一好一坏,问是否有合法方案,使得每个点被确定好坏。

思路:

判断二分图。

先染已知的,再染未知的。

注意判掉没有出现的点。

注意有多个联通块。

 

 

 

codeforces 687 A. NP-Hard Problem(交叉染色法)

题目链接

题意:找两个不相交点集使得对于每一条边至少有一个顶点在点集中

思路:判断能否构成二分图。染色即可。

需要注意的是。。。答案有特判。。和样例不一样我还以为是自己做错了2333.

 

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之前的。。。。我好傻啊。

 

 

hdu 4751 Divide Groups (反向建图,判断二分图,交叉染色法)

hdu 4751 题目链接

题意:n个人,给出每个人认识的人的信息。问能否将这些人分成两组,保证每组至少1个人,并且两两互相认识。

思路:首先是反向建图。由于要求同组内两个人互相认识,那么两个人u,v,只要u不认识v或者v不认识有一个满足,就连接双向边u,v,表示u,v不能分到同一组。

由于图反向以后不保证联通,因此求补图以后可能会得到几个联通分量。

而合法的条件是,每个联通分量都合法。

不合法的条件是,只要由一个联通分量不合法。

以及:之前把交叉染色部分写错了。上道题可以通过纯粹是因为数据水。。?

 

uva 10004 Bicoloring (交叉染色法判断二分图模板题)

uva10004题目链接

题意:给出一个无向图,问是否可以组成二分图。

思路:交叉染色法。

首先任意取出一个顶点进行染色,和该节点相邻的点有三种情况:

          1.未染色    那么继续染色此节点(染色为另一种颜色)

          2.已染色但和当前节点颜色不同      跳过该点

          3.已染色并且和当前节点颜色相同       返回失败(该图不是二分图)

 

学习链接

 

upd:更正dfs中的一个错误。

把dfs(v,1-x)改成了 if (!dfs(v,1-x)) return false;

之前的写法中,当前层之后的层的没有起到任何作用。。。

而实际上应该是后面只要某一层不满足,整体就该为false.

写成这样这题还能过我也是醉了。。。。