学步园

题目链接:  http://poj.org/problem?id=2528 题目大意:   给出一面宽度未知的海报墙                   再给出N张海报，每张海报会贴在墙的区间[a,b]，高度与墙相等                   所有的海报按照顺序贴完，最后可以看到多少张海报(露出来就算) 解题思路:   海报所占用的区间可能会非常大，空间复杂度很高                   所以首先要做的就是离散化所有海报的区间                   如：  1  4                       ...

题目链接：http://poj.org/problem?id=2513 题目大意：   给出无数根筷子，每个筷子头尾各一个单词代表颜色                     颜色相同则可以拼在一起                     如 blue red 的筷子和 red violet 的筷子可以拼在一起                     如 red blue 的筷子和 red violet 的筷子也可以拼在一起                     筷子不分头尾，可以任意调换                     问所有的筷子能否拼成一条线？ 解题思路：  ...

题目链接：http://poj.org/problem?id=2781 题目大意：编号从1~N的网络中，从c1走到c2同学的地方寻求帮助，求使得经过的中间站点最少。  解题思路：简单的最短路问题，两点之间的最短路径，故用SFPA。                     范围1<=N<=105，不能用邻接矩阵，二维数组会爆栈，用邻接链表来处理.             time[i]数组记录走到i点是需要走多少个站点，当第一次走到b点就立刻退出.             time[b]-1既为中间经过的站...

题目链接：  http://poj.org/problem?id=3615 题目大意：  给出有N个顶点M条边的有向连通图                     H可以抽象为每条路的长度                     询问T次，每次询问的内容是：                     A到B点能走的所有路中最长的那段路最短是多少？ 解题思路：  最长的那段路最短是多少，可以用Floyd枚举每一条边                     先加入的一个点k，判断 i---->k点 和 k点--->j点 的最大值         ...

题目链接:   http://poj.org/problem?id=1847 题目大意:  这道题理解起来有点恶心                  有N个铁轨交叉口，这些交叉口与其他交叉口通过铁轨连接                  电车开进一个交叉口，想去另一个交叉口，必须要把灯照向下一个交叉口                  求从A到B驾驶员需要转换灯的最小次数 解题思路:  这道题关键在于构图，每一个交叉点连接的第一条边为0                  其他的边为1，求A到B的最短路径        ...

题目链接:    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]: ...

题目链接:    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点的间接路径，但是矩阵的更新总是受到上一次更新的影...

题目链接：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...

题目链接：  http://poj.org/problem?id=3522 题目大意：  在一个无向联通图中                     求一棵最大边与最小边差值的生成树 解题思路：  最大边与最小边差值的生成树                     换言之使得最小边与最大边的长度最接近                     任取一条边为生成树最小的边，唯一存在一条最大边最接近最小的边                     对所有的边从小到大排序                     差值最小的最大边一定在最小边...

题目链接：http://poj.org/problem?id=2362 题目大意：给出M条筷子，问是否能够拼凑成正方形，是则打印yes，否则no. 解题思路：范围4 <= M <= 20，可以直接用DFS，DFS需要剪枝，否则肯定超时.                   剪枝：1.总数不能被4整除，直接打印 no;                              2.最长的那个筷子大于平均数，直接打印 no;                          ***3.从某点出发,走了很多个点，如果会返回那么直接退出此次循环...