SPFA算法
??SPFA算法在BellmanFord算法的基础上，通过队列的方式，减少了松弛的次数。队列中存储被成功松弛的点，如果邻接点成功松弛，则将其加入到队列中。
??下面为利用SPFA计算最长路的C++代码。
struct Edge {
int to, w;
};
vector<Edge>G[maxn];
int dis[maxn];
bool vis[maxn];
void spfa(int s) {
for (int i = 1; i <= n; i++) {
dis[i] = -INT_MAX;
vis[i] = false;
}
dis[s] = 0;
vis[s] = true;
q.push(s);
while (!q.empty()) {
int u = q.front(); q.pop();
vis[u] = false;
for (auto e : G[u]) {
if (dis[e.to] < dis[u] + e.w) {
dis[e.to] = dis[u] + e.w;
if (!vis[e.to]) {
q.push(e.to);
vis[e.to] = true;
}
}
}
}
}
??在while循环中，当弹出队首元素之后，一定要将vis[u]置为false。
??如果需要计算最短路，只需要修改初始化的dis的值为INT_MAX以及while循环中的松弛条件的<改为>。
差分约束系统
??求解差分约束系统的问题，最终都可以转换为图论中的单源最短路的问题。
??如果有不等式 xi-xj<=a, 则可以另xi=dis[i], xj=dis[j], a=w(i,j)，则等价于dis[i]<=dis[j]+w(i,j)，意味着从节点j到节点i连一条长度为a的有向边。如果令x1=0，则xi=dis[i]便是差分约束问题的一组解。
??利用最短路求解差分约束的关键点如下：
??1. 寻找带减号的不等式（如果满足xi/xj<=k, 则可通过取对数的方法进行转换）（有时候根据题目的条件列出来的不等式是关于和的不等式，可以通过构造前缀和的方法进行转换）
??2. 是否满足起始条件x1=0
??3. 如果有其它的显而易见的约束，如保证结果为正数，也需要建立约束
??4. 如果是求最小解，则构建>=的不等式并跑最长路。反之，构建<=的不等式并跑最短路（一般用spfa跑）
下面给出例题CSP201809-4 再卖菜
#include <bits/stdc++.h>
using namespace std;
#define maxn 310
struct Edge {
int v, w;
};
vector<Edge>G[maxn];
void add(int u, int v, int w) {
G[u].push_back({ v,w });
}
int n;
int dis[maxn];
bool vis[maxn];
int b[maxn];
queue<int> q;
void spfa(int s) {
for (int i = 1; i <= n; i++) {
dis[i] = -INT_MAX;
vis[i] = false;
}
dis[s] = 0;
vis[s] = true;
q.push(s);
while (!q.empty()) {
int u = q.front(); q.pop();
vis[u] = false;
for (auto e : G[u]) {
if (dis[e.v] < dis[u] + e.w) {
dis[e.v] = dis[u] + e.w;
if (!vis[e.v]) {
q.push(e.v);
vis[e.v] = true;
}
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n; i++) {
int j;
cin >> j;
b[i] = j;
}
add(0, 2, 2 * b[1]);
add(2, 0, -(2 * b[1] + 1));
add(n - 2, n, 2 * b[n]);
add(n, n - 2, -(2 * b[n] + 1));
for (int i = 2; i <= n; i++) {
add(i - 2, i + 1, 3 * b[i]);
add(i + 1, i - 2, -(3 * b[i] + 2));
}
for (int i = 1; i <= n; i++) {
add(i - 1, i, 1);
}
spfa(0);
for (int i = 1; i <= n; ++i) {
cout << dis[i] - dis[i - 1] << " ";
}
}
|