这几天学校女生节，挺累的，感觉还是挺好玩的，前几天看了一下最短路，Bellman-fort算法果然比较厉害，今天又参考了刘汝佳的两本书，有了一点新的认识。
废话不说，先上代码：
#include <bits/stdc++.h>
using namespace std; const int INF = 0x3f3f3f3f;
const int maxn = ; struct Edge
{
int from,to;
int dist;
}; struct BellmanFord
{
int n,m;
vector<Edge> edges;
vector<int> G[maxn];
bool inq[maxn];
int d[maxn];
int p[maxn];
int cnt[maxn]; void init(int n)
{
this->n = n;
for(int i=; i<n; i++) G[i].clear();
edges.clear();
} void AddEdge(int from,int to,int dist)
{
edges.push_back((Edge)
{
from,to,dist
});
m = edges.size();
G[from].push_back(m-);
} bool negativeCycle(int s)
{
queue<int> Q;
memset(inq,,sizeof(inq));
memset(cnt,,sizeof(cnt)); for(int i=; i<n; i++)
{
d[i] = INF;
} d[s] = ;
inq[s] = true;
Q.push(s); while(!Q.empty())
{
int u = Q.front();
Q.pop();
inq[u] = false;
for(int i=; i<G[u].size(); i++)
{
Edge& e = edges[G[u][i]];
if(d[u]<INF&&d[e.to]>d[u]+e.dist)
{
d[e.to] = d[u] + e.dist;
p[e.to] = G[u][i];
if(!inq[e.to])
{
Q.push(e.to);
inq[e.to] = true;
if(++cnt[e.to]>n)
return false;
}
}
}
}
return true;
} }; struct BellmanFord
{
int n,m;
vector<Edge> edges;
vector<int> G[maxn];
bool inq[maxn];
int d[maxn];
int p[maxn];
int cnt[maxn]; void init(int n)
{
this->n = n;
for(int i=; i<n; i++) G[i].clear();
edges.clear();
} void AddEdge(int from,int to,int dist)
{
edges.push_back((Edge)
{
from,to,dist
});
m = edges.size();
G[from].push_back(m-);
} bool negativeCycle()
{
queue<int> Q;
memset(inq,,sizeof(inq));
memset(cnt,,sizeof(cnt));
for(int i=; i<n; i++)
{
d[i] = ;
inq[] = true;
Q.push(i);
} while(!Q.empty())
{
int u = Q.front();
Q.pop();
inq[u] = false;
for(int i=; i<G[u].size(); i++)
{
Edge& e = edges[G[u][i]];
if(d[e.to]>d[u]+e.dist)
{
d[e.to] = d[u] + e.dist;
p[e.to] = G[u][i];
if(!inq[e.to]) {
Q.push(e.to);
inq[e.to] = true;
if(++cnt[e.to]>n)
return true;
}
}
}
}
return false;
} };
第一个Bellman-Ford算法是紫书上的；
解析：
1、起点入队列
2、初始化点到起点的距离是INF；
3、和Dijkstra相比，每个结点可以多次加入（如果有负环，那么这个结点是可以多次松弛的，一旦次数无穷就说明了这的确是个负环）；
4、因为是从起点出发的，然后在搜索邻接表，没有找到负环，只能说明，从起点到不了负环，但是可能是有负环的。没有负环，最短路数组 d 是正确可用的。
第二个Bellman-Ford算法是白书上的；
解析：
1、Bellman-Ford 算法一个重要应用就是判负环，上面的一个起点入队列，就要改成所有点入队列。
2、初始化 d 数组为 0：
可以从第二图中，有一个负环，但是从 0 ，无法松弛；但是，在队列中，从 1 开始搜索的时候，还是可以松弛，并且找到这个负环；然后由于每个结点之前都入过队列，就能保证找到那个负环。