现在位置: 首页 > 算法 > 文章
2018年09月22日 算法 ⁄ 共 1573字 评论关闭
题目链接:http://poj.org/problem?id=2513 题目大意:   给出无数根筷子,每个筷子头尾各一个单词代表颜色                     颜色相同则可以拼在一起                     如 blue red 的筷子和 red violet 的筷子可以拼在一起                     如 red blue 的筷子和 red violet 的筷子也可以拼在一起                     筷子不分头尾,可以任意调换                     问所有的筷子能否拼成一条线? 解题思路:  ...
阅读全文
2018年09月22日 算法 ⁄ 共 1210字 评论关闭
题目链接:http://poj.org/problem?id=2781 题目大意:编号从1~N的网络中,从c1走到c2同学的地方寻求帮助,求使得经过的中间站点最少。  解题思路:简单的最短路问题,两点之间的最短路径,故用SFPA。                     范围1<=N<=105,不能用邻接矩阵,二维数组会爆栈,用邻接链表来处理.             time[i]数组记录走到i点是需要走多少个站点,当第一次走到b点就立刻退出.             time[b]-1既为中间经过的站...
阅读全文
2018年09月22日 算法 ⁄ 共 1131字 评论关闭
题目链接:  http://poj.org/problem?id=3615 题目大意:  给出有N个顶点M条边的有向连通图                     H可以抽象为每条路的长度                     询问T次,每次询问的内容是:                     A到B点能走的所有路中最长的那段路最短是多少? 解题思路:  最长的那段路最短是多少,可以用Floyd枚举每一条边                     先加入的一个点k,判断 i---->k点 和 k点--->j点 的最大值         ...
阅读全文
2018年09月22日 算法 ⁄ 共 1366字 评论关闭
题目链接:   http://poj.org/problem?id=1847 题目大意:  这道题理解起来有点恶心                  有N个铁轨交叉口,这些交叉口与其他交叉口通过铁轨连接                  电车开进一个交叉口,想去另一个交叉口,必须要把灯照向下一个交叉口                  求从A到B驾驶员需要转换灯的最小次数 解题思路:  这道题关键在于构图,每一个交叉点连接的第一条边为0                  其他的边为1,求A到B的最短路径        ...
阅读全文
2018年09月22日 算法 ⁄ 共 2201字 评论关闭
题目链接:    http://poj.org/problem?id=2449 题目大意:    在一个有N个点M条边的有向连通图里                    找到S到T的第k短路的长度 解题思路:    经典的k短路A*算法题                    估价函数: f[x]=h[x]+g[x]                    f[x]:  估计经过该点的路线到达T点最小需要经过的路径长度 (大于或等于实际最短长度)                    h[x]:  从起点到该点实际走的长度 (已经走了)                    g[x]: ...
阅读全文
2018年09月22日 算法 ⁄ 共 2146字 评论关闭
题目链接:    http://poj.org/problem?id=3613 题目大意:    给出一张无向连通图,求S到E经过k条边的最短路。 解题思路:    利用递推的思路,先算出经过一条边的最短路,再算两条边......k-1条边,k条边的最短路                    先看一下Floyd的核心思想: edge[i][j]=min(edge[i][j],edge[i][k]+edge[k][j])                    i到j的最短路是i到j的直接路径或者经过k点的间接路径,但是矩阵的更新总是受到上一次更新的影...
阅读全文
2018年09月22日 算法 ⁄ 共 887字 评论关闭
题目链接:http://poj.org/problem?id=2485 题目大意:给出1~N的城镇,现在需要修一条高速公路,使得任意城镇可以互相来往; 转换之后就成了求最小生成树中最长的边  解题思路:input的是邻接矩阵,直接用 prim 算法 代码: #include <stdio.h> #include <string.h> #define MAX 501 #define INF 0x3f3f3f3f int t,n,nears[MAX],edge[MAX][MAX]; // near存储连接i点最短的边是near[i] int Prim (int v0) //从v0...
阅读全文
2018年09月22日 算法 ⁄ 共 1457字 评论关闭
题目链接:  http://poj.org/problem?id=3522 题目大意:  在一个无向联通图中                     求一棵最大边与最小边差值的生成树 解题思路:  最大边与最小边差值的生成树                     换言之使得最小边与最大边的长度最接近                     任取一条边为生成树最小的边,唯一存在一条最大边最接近最小的边                     对所有的边从小到大排序                     差值最小的最大边一定在最小边...
阅读全文
2018年09月22日 算法 ⁄ 共 1524字 评论关闭
题目链接:http://poj.org/problem?id=2362 题目大意:给出M条筷子,问是否能够拼凑成正方形,是则打印yes,否则no. 解题思路:范围4 <= M <= 20,可以直接用DFS,DFS需要剪枝,否则肯定超时.                   剪枝:1.总数不能被4整除,直接打印 no;                              2.最长的那个筷子大于平均数,直接打印 no;                          ***3.从某点出发,走了很多个点,如果会返回那么直接退出此次循环...
阅读全文
2018年09月22日 算法 ⁄ 共 969字 评论关闭
题目链接:   http://poj.org/problem?id=1200 题目大意:  给出两个数字N和NC,一行字符串                     这行字符串最多出现NC个字符                     寻找长度为N的不同子串个数 解题思路:   字符串的长度最长为1600万,用strcmp()函数判断次数太多,肯定会TLE                     开始用了BKDRHask,和ELFHask都WA,说明有些字串的hash值相等                     为了避免这种情况我用链表来处理冲突,但是爆...
阅读全文