poj 1422题目链接 题意+思路：DAG的最小路径覆盖。。。匈牙利算法。。。poj 2594的低配版。。 /* *********************************************** Author :111qqz Created Time :2016年05月26日 星期四 20时24分15秒 File Name :code/poj/r2594.cpp ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> …

poj 2594 题目链接 题意：一个DAG图，每个点有宝藏...可以降落任意个机器人到任意点...然后机器人可以沿着路径走，路过某个点的时候，可以取走该点的宝藏。问要取走所有宝藏，最少需要多少个机器人。 思路：乍一看。。很像DAG图的最小路径覆盖。。但是最小路径覆盖是要求每个点只能经过一次的。。而这道题路过某个点的时候，可以不取走宝藏。。以及题面里明确说了“you should notice that the roads of two different robots may contain some same point. ” 那是否还可以用最小路径覆盖做呢。。答案是可以的。。。 区别就在于一个点如果被一条路径使用过一次，还可不 …

poj 2446 题目链接 题意：一个nm的矩形方格里，有k个坏点，然后问能否用12的矩形块将矩形方格填满。坏点不能填，小的矩形块不能重叠，不能超出边界。不能有好点没有被填。 思路：乍一看没什么好的思路。。。然后发现小的矩形块只能有两种放置方法（横着放，竖着放） 可能我们对于第i个，可以横着放，也可以竖着放，但是可能某种方案使得后面的某一块没办法放置，因此我们需要反过来调整第i块的放法。 这个过程似乎和二分图匹配有点类似。。？ 那到底有没有相似点呢。。。又如何划分集合呢。。。？ 如果每个小方格看做点，能不能填满，其实就等价与这些点的最大匹配数×2+坏点数=mn是否成立。。。那如何划分集合呢。。。？ 我们可以根据点的坐标的奇偶性划分集 …

poj 1274题目链接 裸的匈牙利。 /* *********************************************** Author :111qqz Created Time :2016年05月25日 星期三 17时49分22秒 File Name :code/poj/1274.cpp ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include …

hdu2063题目链接 题意：求二分图最大匹配。 思路：匈牙利算法。 通过这三篇博客了解了相关概念，学习了匈牙利算法。 趣写算法系列之--匈牙利算法 二分图的最大匹配、完美匹配和匈牙利算法 匈牙利算法详解 感受就是：这个是相对容易学的算法。。并没有名字那么不明觉厉。。。 主体就是一个dfs的过程。。。。 不过据说有比较多的应用。 所以打算切一些题目加深理解以后再回来总结。 /* *********************************************** Author :111qqz Created Time :2016年05月25日 星期三 16时51分32秒 File Name …