现在位置: 首页 > 算法 > 文章
2018年09月22日 算法 ⁄ 共 969字 评论关闭
题目链接:   http://poj.org/problem?id=1200 题目大意:  给出两个数字N和NC,一行字符串                     这行字符串最多出现NC个字符                     寻找长度为N的不同子串个数 解题思路:   字符串的长度最长为1600万,用strcmp()函数判断次数太多,肯定会TLE                     开始用了BKDRHask,和ELFHask都WA,说明有些字串的hash值相等                     为了避免这种情况我用链表来处理冲突,但是爆...
阅读全文
2018年09月22日 算法 ⁄ 共 1441字 评论关闭
题目链接:   zoj 2588 题目大意:   在无向连通图中找桥,并且按序号输出 解题思路:   Tarjan查找割边                   数据中可能会出现重边,需要判断是否是重边                   每次加入新的边,则枚举此顶点之前加入的边中是否存在另一点                   low[vv]>dnf[u]是桥,low[vv]>=dnf[u]是割点 代码: //Final Tarjan 找桥(割边) #include <stdio.h> #include <string.h> #include <std...
阅读全文
2018年09月22日 算法 ⁄ 共 1605字 评论关闭
题目链接:    zoj 1654 题目大意:   给出NxM的地图,地图上有空地,草地和墙                   要在空地上放置机器人,机器人可向上下左右四个方向发射激光                   且防止的机器人不会被其他机器人的激光射到,机器人可以穿过草地但不能穿墙                   问可以放置机器人的最大数目 解题思路:   先把同一行的空地和草地构成块(中间无墙),若中间有墙则可以构成多个块                   再把列按同样的方式...
阅读全文
2018年09月22日 算法 ⁄ 共 633字 评论关闭
题目链接:   poj 1961 题目大意:   给定字符串,找出他所有的前缀的最小循环节的长度 解题思路:   思路与2406一样                   Tlen%(Tlen-next[Tlen])==0则Tlen-next[Tlen]是最小循环节                   证明过程参考2406的解题报告                   这里需要多次查询处理 代码: #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX 1000010 int next[MAX],Tlen; char ch[...
阅读全文
2018年09月22日 算法 ⁄ 共 1510字 评论关闭
题目链接:   hdu 1269 题目大意:   给定n个字符串,找出最长的公共子串,不存在输出 no significant commonalities 解题思路:   选出长度最短的字符串,枚举它的子串                   把它的子串分别与其余的n-1个字符串匹配                   字符串长度越短它的子串就越少,枚举量越少                   枚举子串的顺序从大到小,能够匹配就退出输出答案                   如果从小到大枚举则需要枚举所有符合情况的子...
阅读全文
2018年09月22日 算法 ⁄ 共 746字 评论关闭
题目链接:   poj 3041 题目大意:   给出NxN的矩阵,有M个点是障碍                   每次只能删除一行或者一列,最少删除多少次才能清除障碍 解题思路:   行作为X集合,列作为Y集合,障碍就是两集合间的连线                   问题转化为如何使得选取最少的点,覆盖掉所有的直线                   由König定理可得 最小点集覆盖==最大匹配数,匈牙利求最大匹配 代码: #include <stdio.h> #include <string.h>...
阅读全文
2018年09月22日 算法 ⁄ 共 760字 评论关闭
题目链接:   poj 1274 题目大意:   给出N头奶牛,和M个牛棚                   每头奶牛只在自己喜欢的牛棚产奶,问最大的产牛量 解题思路:   把N头奶牛作为X集合,M个牛棚作为Y集合                   奶牛和牛棚的关系就是集合X和集合Y的关系                   问题转化为 X集合和Y集合的最大匹配数                   匈牙利DFS增广路求解 代码: #include <stdio.h> #include <stdlib.h> #include <string...
阅读全文
2018年09月22日 算法 ⁄ 共 1547字 评论关闭
题目链接:   poj 1273 题目大意:   有N个点和M条边,每条边最大的流量为c,初始流量为0                   1为源点,n为汇点求最大流 解题思路:   最短增广路算法比一般增广路算法每次增广大范围小,因为每次增广都在残留网络进行                   但是最短增广路每次还是要回到源点继续增广,而连续最短增广路算法则利用深搜的思想                   一次遍历就能把残留网络增广完毕                   PS:用邻接表时要注...
阅读全文
2018年09月22日 算法 ⁄ 共 1923字 评论关闭
题目链接:   poj 1689 题目大意:   有个人想拍n部电影,每部电影限定每周哪几天可以拍                   并且必须在第ki周之前把这部电影拍完,问能否拍完n部电影 解题思路:  把每部电影当作一个顶点,源点指向这些顶点,容量为该电影需要拍多少天                   然后把每一天都当作顶点,某个工作可以在这天完成就连容量为1大边                   每天的顶点指向汇点,容量也为1                   最后求出最大流,满...
阅读全文
2018年09月22日 算法 ⁄ 共 2273字 评论关闭
题目链接:   poj 2195 题目大意:   给出NxM的地图,'.'表示可以走的,'H'表示家,'m'表示人,H和m的数目相同                   求把所有人移动到H的最小步数 解题思路:   建立超级源点,分别连接每个m,容量为1,费用0                   建立超级汇点,分别把每个H连接到汇点,容量为1,费用为0                   再把每个m分别指向H,容量为1,费用为该m到H的横纵左边之差的绝对值的和,|X1-X2|+|Y1-Y2|                  ...
阅读全文