poj 1325 题目链接 题意：有两台机器A和B,分别有n和m种工作模式。 现在有k个job,三元组（i,x,y),job i可以用A机器的x模式完成或者用B机器的y模式完成。初始两个机器都在模式0.机器更换模式的时候需要重启，问最少的重启次数。 思路：这道题的难点在于建图。。。每个job恰好对应了两种模式。。那么如果把模式看成点。。边就对应了这个job。。这样就是一个二分图。。。至于方向。。。怎么指都可以。。。统一就行。。 完全没有图的影子的题依然可以用图论解决。。。而且算是加深了对图这种模型的理解把。 然后这道题就变成了二分图的最小顶点覆盖。 **二分图中，选取最少的点数，使这些点和所有的边都有关联（把所有的边的覆盖），叫做最 …

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 …

uva10986题目链接 题意：裸的spfa. 思路：模板，1A. /* *********************************************** Author :111qqz Created Time :2016年05月25日 星期三 03时25分27秒 File Name :code/uva/10986.cpp ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include …

poj2949 题目链接 题意：我们有 n 个 (n<=100000) 字符串,每个字符串都是由 a~z 的小写英文字 母组成的字符串。如果字符串 A 的结尾两个字符刚好与字符串 B 的开头两字符相 匹配,那么我们称 A 与 B 能相连(注意: A 能与 B 相连不代表 B 能与 A 相连)。 我们希望从给定的字符串中找出一些,使得他们首尾相接形成一个环串(一个串首尾相连也算) 我们想要使这个环串的平均长度最长。 思路：参考了国家集训队论文《spfa算法的优化与应用》 首先我卡在了关于接龙问题的处理方法，只能想到n^2的方法。。显然gg. 而正解是把每个单词看做一条边，把每个单词开头的两个字母和结尾两个字母看做起点和终点，由于 …

poj 1860 题目链接 题意：有n种货币，m个货币交易点，每个货币交易点只能是两种货币之间交换，给出两个方向的汇率和手续费。初始拥有数量v的货币s,问能否经过一些py交易，使得最后手里的货币s比v多。 思路：大概还是用spfa求最长路。。松弛那里需要注意一下算法。。。 1A。。。好爽啊。。。。。 /* *********************************************** Author :111qqz Created Time :2016年05月24日 星期二 23时41分46秒 File Name :code/poj/1860.cpp …

poj1932题目链接 题意：初始在点1，有100点能量，然后每个点有一个能量值【-100,100】，经过某个点会加上这个点的能量值，问能否找到一条到点n且的路线，且路径任何点的能量值一直为正。一共不超过100个点。 思路：像样例中是直接联通，一路上的能量值都大于0，这是有解的一种情况。另一种是存在一个正环，可能一次路过后面的能量值不够，但是我们可以走多次啊。 因为要求每一步的能量值都大于0，那么我们可以初始化d[]数组为0，然后用spfa求最长路（只需要把那个三角形等式换个方向即可） 如果可以直接联通，也就是d[n]>0，那么有解。 还有可能是存在一个环（判断环的方法是用一个数组在spfa的时候统计每个点入队的次数，如果一个 …