恩，本篇文章再写一点深入的思考。忽然发现我的博客开始走找各种被人忽略的细节的路线了。今天要为大家带来的是差分约束的两个题，并且会为大家说明一下自己做这题时候的思考和网上流传的一些错误，不想让网上抄来抄去的东西误导了大家的思路。OJ数据弱，这个是真的，题目那么多，不能保证每个题测试数据的质量，所以很多错误的程序也能过，导致了大家可能把错误的思路也认为是正确的了。恩，下面开始正文。
题意：n头牛站在x轴上，并且x[1]<=x[2]<=...<=x[n]，然后给定了一些喜欢的关系和讨厌的关系，喜欢的关系是（a，b，c）代表牛a和牛b的距离不才能超过c，讨厌的关系也是（a，b，c）代表牛a和牛b的距离至少是c，然后求牛1和牛n的最大距离是多少。如果没有合法的站位，输出-1；如果牛1和牛n可以无穷远，输出-2；否则输出牛1和牛n的最大距离。
这个题看上去很水的，差分约束的题，按照“最长路求最小值，最短路求最大值”的理论建图就行了。需要注意的一个细节就是，如果同时满足没有合法的站位和牛n牛1可以相距无穷远，那么按照题意应该是输出-1的 ...
写个博客记录一下最短路的几种算法，尽量做最正确的解答，减少大家的疑惑，网上有好多讲的都抄来抄去，还有好多讲的都是错误的。。。
熟悉的最短路算法就几种：bellman-ford，dijkstra，spfa，floyd，下面针对这几个算法具体解析一下。
首先说明一点，就是关于负环的问题。
bellman-ford可以用于边权为负的图中，图里有负环也可以，如果有负环，算法会检测出负环。
dijkstra只能用于边权都为正的图中。
spfa是个bellman-ford的优化算法，本质是bellman-ford，所以适用性和bellman-ford一样。
floyd可以用于有负权的图中，即使有负环，算法也可以检测出来。
任何题目中都要注意的有四点事项：图是有向图还是无向图、是否有负权边，是否有重边，顶点到自身的可达性。这几点非常重要，可以在我下面的讲解中体会。
这个最简单，只能在边权都为正的图中用这个算法，不论是有向图还是无向图。算法是个贪心的过程，每次拿出一个没有被标记过的距离最小的顶点，并从这个点进行扩展，也就是尝试松弛从这个点出发的每条边。为什么一定要用在正权图中呢？因为算法的过程相当于把整个图中的点一个一个加入到“处理完”集合S的过程，并且处理完集合中的点的距离一定是从源点到该点的最小距离。如果图中有负权，会导致一个进入集合中的点可能在后面的过程中距离值变得更小，算法就错了。举个例子来说：有向图 ...
题意：一个无向图，求从一个顶点到另一个顶点的恰好经过k条边的最短路径，可能有自环，无重边。
分析：这个题其实就是矩阵乘法，用了dp的思想，dp[k][i][j]代表恰好经过k条边的i到j的最短路，那么dp[k][i][j]=min{dp[k-1][i][p]+g[p][j]}（其中g是原图）。可以用矩阵乘法来做，因为对于dp[k-1][i][j]来说，只要乘以一次原图矩阵，就相当于做了一次转移，得到的就是dp[k][][]矩阵。我想说这个题除了状态设计和floyd稍微沾了一点边之外，其他一点关系都没有了，竟然看到网上好多人用写floyd的循环顺序来写这个题，真是令人费解，这个题只是改了矩阵乘法的最内层，改变了矩阵乘法的运算规则，和floyd真的没关系啊！！！
另外，矩阵乘法的规则和在图中求一个点到另一个点的恰好经过k条边的方法数的规则是一样的，二者的状态转移方程也是一样的，所以矩阵乘法不需要经过任何修改就能做这种求恰好经过k条边的方法数的题，而不用像这个题还得做些修改。这些题都需要注意初始化的东西 ...
题意：一个无向图，所有边权为正，求这个无向图中的一个权值最小的环（环的权值定义为环中所有边权值的和）。要求环的顶点数至少为3个，且图中可能存在重边。
分析：这个题我最开始只有搜索的想法，后来看到了floyd的做法，才折服了，向强大的floyd致敬！ 这个题可以这么想，抛开floyd的思路，我们知道每个环中都有一个顶点标号最大的顶点（比如为k）。我们可以枚举这个顶点，枚举完这个顶点之后我们再枚举另外两个和它相邻的顶点i和j（i，j < k）。如果这个时候我们知道i到j的不经过k的最短路（设为p），那么我们就可以把边i->k，k->j和路径p组合起来，成为一个环，如果这个环的权值小于当前求出的所有环里面的最小权值的话，那么就更新一下最小值，并记录路径。
恩，这个思路看上去是挺好的，但是我们怎么求i到j的不经过k的最短路呢？想到了什么？floyd！ floyd的本质是个dp，dp[k][i][j]代表i到j的中间节点（不包括i和j）都在区间[1，k]时，i到j的最短路。floyd算法的最外层循环是个从小到大枚举k的过程，当最外层刚刚进入第k次循环的时候 ...
题意：一个图，有两种边，一种是双向边，权值为正，一种是单向边，权值为负。
问能否在图中找到一个负环。
分析：典型的找负环的题，但是这个题没有规定起点，所以直接从点1开始做bf是错误的。
bellman-ford算法可以判断一个从源点可达的环，那这个题需要做n次bf吗？
其实可以建立一个源，从源向每个图中的点引一条任意权值的边（不必为0），然后用bf就行了。
本质上就是初始化和经典的初始化不同，细节见代码。
/*
POJ 3259
code by heifrank
*/
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int MV = 505;
vector< pair<int, int> > G[MV];
int d ...Page 1 / 1