Spfa最短路算法，属于单源最短路，可以存在负权边，可以判断负环。 Spfa的算法思想从源点层层松弛，达到全图的单源最短。 题目：HDU 3790（题意很简单） 注意：输入边的信息的时候，用scanf，别用cin，会超时。 #include<iostream>#include<cstring>#include<vector>#include<queue>#include<cstdi

一种单源最短路算法，只能用于边权为正的图中。 该算法的思想非常简单，在某一时刻，整个图的点被分为两个部分： 第一部分：包含源点，已经知道了这部分中其它点到达源点的最短距离。 第二部分：知道了该部分所有的点到达第一部分中的点的最近距离。 在该算法中可以使用优先队列进行优化，代替原有的暴力FOR循环。 题目：HDU 3665（题意简单） 思想：从0点出发，求出到达所有海边城市的最短路，然后

Floyd最短路算法属于多源最短路，可以求出图中任意两点的最短路径。如果图中存在负权但是不存在负环的话Floyd是可以解决最短路问题的。 Floyd算法返回最短路径：多源最短路，需要二维空间的数组来存储所有的最短路径，path[i][j]，其中 i 表示起点，j 表示终点，那么path[i][j]表示以 j 为终点，i 为起点的最短路径上点 i 的下一个节点。那么在初始化过程中path[i][j

给定点的先后出场次序：例如 点 u 出场的前提是点 v 已经出现，那么这就代表了一个约束条件，现在给出很多的约束条件，用程序来给这些点的出场次序排个序，要求满足所有的约束条件问题，这时候用到的就是拓扑排序。 拓扑排序用于有向无环图，如果过要是想判断一个有向图是否存在环，可以使用拓扑排序进行判断（如果提取入度为0的点的个数没有达到所有点的个数，那么就一定出现环了） 有关拓扑排序的输出问题：

在当前的状态下搜索所有可能的状态，1）队列内的顺序问题；2）搜索时的各种判断问题，边界等等。 题目：HDU 1880 （中文题目） 思想：典型的广搜问题，注意三点： 1）如果下一个地点是梯子，要判断梯子的方向和人的走向是否一致 2）因为题目要求到达T的最少时间，所以要用到优先队列来代替传统的队列 3）如果下一个点是梯子，但是不能走，那么此时增加了一种搜索方向，那就是原地不动，也要推入队列

2-SAT团问题：给出 n 个布尔变量（取值0 或 1），之后再给出 m 个有关这些变量的约束条件，设其中有i，j两个变量 必须选择 i必须不选 ii 和 j 中选择一个i 和 j 不都选择i 和 j 选择的情况相同i 和 j 选择的情况相反 问：能否将这 n 个布尔变量分成两个组分，并且满足给定的这 m 个约束条件。 解决方案： 1. 建图假设 i  的对立面是  必须选择 i ：必