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

题意:

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

思路:

判断二分图。

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

注意判掉没有出现的点。

注意有多个联通块。

&[……]

Read more

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

题目链接

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

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

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

 

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

题目链接:hdu 5285 题目lianjie

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

思路:。。。一开始看到n的数据范围。。。想当然的以为会给认识的人的关系。。。[……]

Read more

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

hdu 4751 题目链接

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

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

Read more

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

uva10004题目链接

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

思路:交叉染色法。

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

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

          2.已染色但和当前节点颜[……]

Read more