题目链接 题意：找两个不相交点集使得对于每一条边至少有一个顶点在点集中 思路：判断能否构成二分图。染色即可。 需要注意的是。。。答案有特判。。和样例不一样我还以为是自己做错了2333. /* *********************************************** Author :111qqz Created Time :2016年09月03日 星期六 01时04分40秒 File Name :code/hdu/687A.cpp ************************************************ */ #include <cstdio> #include …

题目链接：题目链接 题意：给出一个无向图，该图是通过仅包含‘a’ 'b' 'c'三个字母，以规则“i,j之间有边，当且仅当s[i]和s[j]相同，或者s[i]和s[j]在字母表中相邻”（也就是只有'a'和'c'是没有边相连的）得到的，现在问能否还原这个字符串，如果能，输出任意一个解。 思路：其实就是简单构造。。。 构造的一个技巧是。。把能确定的地方先确定了。。。。 我们发现'b'比较特殊。。因为b和任意点都相连。。。 于是可以统计一下度。。。然后确定字符串中的b 然后对于某个没有确定的位置，我放置一个a,并且把所有和这个位置相连的都放成a 字符串中剩下的没有确定的位置就一定是c了。 这个时候我再判断是否满足题中图的条件。 /* …

题目链接：hdu 5285 题目lianjie 题意：给定n个小朋友，以及小朋友之间的关系，要求将小朋友分成两组，**并且每组至少一个人，**现在问能否这样分组，如果有解，输出两组的人数，并保证第一组的人数尽可能地大。 思路：。。。一开始看到n的数据范围。。。想当然的以为会给认识的人的关系。。。尼玛。。。求个补图就够受的了。。。。不会做，卒。 结果发现。。竟然给的是两个人不认识的关系。。。2333 那么我们来交叉染色。。。 实际上交叉染色的过程中，颜色相同的点属于二分图中相同的点集合。 交叉染色其实是在模拟交错轨的过程...？ 由于图不一定联通，可能由多个联通块。 我们在交叉染色的时候记录一下0,1的个数（也就是两个点集的大小） 然 …

hdu 5215 思路:询问一个无向图，是否存在奇数环，以及是否存在偶数环。（不同的环之间可以由相同的点，不能有相同的边） 思路：一开始的想法是，根据染色的奇偶性，如果染色到某个之前染色过的点，和当前要染的颜色相同，说明存在奇数环，不同，说明存在偶数环。 感觉很有道理的做法。。。然而错了。。。发现是忽略了上面说的，不同的环之间由相同的点的情况。 比如这组数据： 5 6 1 2 2 3 3 1 1 4 4 5 5 1 两个三元环扣在一起。 实际上是既有奇数环，又有偶数环的。 但是按照我的做法，由于每次只去染没有染过的点，无法发现偶数环。 因此正解是增加一步回溯，这样使得之前存在与某个环中的点还可以出现在其他环中。 然而这样复杂度会 …

链接

键盘足够爽了以后。。。 鼠标明显降低效率。。。 学会逐步脱离鼠标吧orz. 首先是chrome插件vimium vimium教程 Vimium 常用的按键功能解释： * **j：向下细微滚动窗口 k：向上细微滚动窗口** * J：(**Shift+j的意思，以下大写全部表示加Shift)** 下一个标签页 K：上一个标签页 * d：向下滚动半个屏幕 u：向上移动半个屏幕 * **g+g（连续按两下g）：回到顶部** * **G：到达页面底部** * H：后退 L： 前进 * f：将当前网页上的所有可见链接/输入框分配一个快捷键，输入后就可以打开或者跳转到对应的输入框。如果按的是F，那么将在新窗口中打开页面（见上图） * g+i：将 …

hdu 2444题目链接 题意：判断一个有向图是否是二分图，是的话求最大匹配数。 思路：交叉染色判二分图，是的话跑遍匈牙利即可。1A. /* *********************************************** Author :111qqz Created Time :2016年09月01日 星期四 14时24分36秒 File Name :code/hdu/2444.cpp ************************************************ */ #include <cstdio> #include <cstring> #include …

hdu 4751 题目链接 题意：n个人，给出每个人认识的人的信息。问能否将这些人分成两组，保证每组至少1个人，并且两两互相认识。 思路：首先是反向建图。由于要求同组内两个人互相认识，那么两个人u,v，只要u不认识v或者v不认识有一个满足，就连接双向边u,v，表示u,v不能分到同一组。 由于图反向以后不保证联通，因此求补图以后可能会得到几个联通分量。 而合法的条件是，每个联通分量都合法。 不合法的条件是，只要由一个联通分量不合法。 以及：之前把交叉染色部分写错了。上道题可以通过纯粹是因为数据水。。？ /* *********************************************** Author :111qqz …

uva10004题目链接 题意：给出一个无向图，问是否可以组成二分图。 思路：交叉染色法。 **首先任意取出一个顶点进行染色,和该节点相邻的点有三种情况:** **　1.未染色 那么继续染色此节点(染色为另一种颜色)** **　2.已染色但和当前节点颜色不同 跳过该点** **　3.已染色并且和当前节点颜色相同 返回失败(该图不是二分图)** 学习链接 upd:更正dfs中的一个错误。 把dfs(v,1-x)改成了 if (!dfs(v,1-x)) return false; 之前的写法中，当前层之后的层的没有起到任何作用。。。 而实际上应该是后面只要某一层不满足，整体就该为false. 写成这样这题还能过我也是醉了。。。。 /* …

3680: 吊打XXX Time Limit: 10 Sec Memory Limit: 128 MBSec Special Judge Submit: 2043 Solved: 732 [Submit][Status][Discuss] Description gty又虐了一场比赛，被虐的蒟蒻们决定吊打gty。gty见大势不好机智的分出了n个分身，但还是被人多势众的蒟蒻抓住了。蒟蒻们将 n个gty吊在n根绳子上，每根绳子穿过天台的一个洞。这n根绳子有一个公共的绳结x。吊好gty后蒟蒻们发现由于每个gty重力不同，绳 结x在移动。蒟蒻wangxz脑洞大开的决定计算出x最后停留处的坐标，由于他太弱了决定向你求助。 不计摩擦，不计能量损 …