苟且的狮子的博客

Graph Coloring I

dfs 题意：分析：深搜没学好啊！我们会发现，这其实就是一个判断图是否是二分图的过程！那么，我们已知，二分图是没有奇数环的。所以，我们可以断定，要不可以染色，要不有奇数环！染色部分容易，广搜深搜都可以，分深度奇偶染色即可。但是，要我们找环，就有点困难了。因为要是环，所以我们选择深搜，因为要...

国政议事

二分图最大匹配，HK算法，暴力枚举题意：分析：这道题是很明显是二分匹配题目。但因为我初学二分图所以刚开始并没有看出如何建立二分图的。我是想，对于人：1,2,3,4,5,6,7,8在刚开始匹配，1去将他手中的一个任务交给5然后到2开始交任务，如果2也有一个要交给5的任务，那么此时他发现5已经有...

[TJOI2013]攻击装置

二分图最大匹配题意：分析：经典的求最大子集的问题。我们先求最大匹配。最大子集 = 总定点数 - 最大匹配选择你的算法，我选择HK算法！但是摆在我们面前的还有一个问题：如何区分图中顶点所在的集合？ 1.染色法：我们连完边建完图后，进行搜索，搜索深度为奇数的为一个子集，为偶数的为一个子集 2...