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 5215 Cycle(交叉染色法判断无向图的奇偶环)

hdu 5215

思路:询问一个无向图,是否存在奇数环,以及是否存在偶数环。(不同的环之间可以由相同的点,不能有相同的边)

思路:一开始的想法是,根据染色的奇偶性,如果染色到某个之前染色过的点,和当前要染的颜色相同,说明存在奇数环,不同,说明存在偶数环。

感觉很有道理的做法。。。然而错了。。。发现是忽略了上面说的,不同的环之间由相同的点的情况。

比如这组数据:

5 6

1 2

2 3

3 1

1 4

4 5

5 1

两个三元环扣在一起。

实际上是既有奇数环,又有偶数环的。

但是按照我的做法,由于每次只去染没有染过的点,无法发现偶数环。

因此正解是增加一步回溯,这样使得之前存在与某个环中的点还可以出现在其他环中。

然而这样复杂度会炸。。。

于是我们根据,每条边只能走一次,对边加一个vis,使得每条边只走一次,从而保证复杂度。

好题!

这道题我看到了三种解法,第一种是官方解法,tarjan什么(没仔细看)。

第二种是交叉染色。

但是我们可以发现,在这样的情况下,偶环是否和奇环是有联系的,即能不能根据两个奇环的关系,来判断偶环是否存在。

做法:判断是否存在一个点,同时属于两个奇环,如果存在,那么这两个奇环一定可以构成偶环。

证明:令两个奇环分别有x1、x2条边,如果两个环存在一个公共点,令他们存在y条公共边,则它们合并成的环有x1+x2-2*y条边,一定是偶环。因为题目中限制的是边的通过次数,所以即使像下面这组数据一样y=0,偶环是交叉的,也是符合题意的。

 
第二种做法

但是代码略长,而且还要记录路径。

第三种做法就是我这里用到的做法。。。感觉很完美。。可以当模板23333

 

 

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.

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