<—点个赞吧QwQ
宣传一下算法提高课整理{:target=”_blank”}
SPFA
将农场抽象成图结构,每条边到底代表道路还是虫洞,不做事先区分,其权值统一为到达时刻与出发时刻的时间差,对于道路来说这个值是正数,而对于虫洞来说这个值是负数
如果“想看到出发前的自己”,就要求从某节点出发,经过若干条边后,回到该节点的时刻与出发时刻的时间差小于0,这和最短路问题中的“死锁”,也就是存在负权回路的情况完全一致
至于为什么把负权回路称为死锁,原因就是搜索最短路的过程中,无论从哪个节点进入回路,最短路径长度都会被无限次更新,与操作系统中资源的无限等待类似。
不存在死锁的情况下,一个节点更新最短路的次数最多为n-1次,如果它更新次数不小于n次了,就可以直接判断死锁成立,细节见注释
时间复杂度
$O(n*(2m+w))$,n,m,w分别为节点,道路和虫洞的数量
注意spfa本质上是用队列辅助的Bellman-Ford算法,没有改变其原本的复杂度,图结构没有负权边不建议各位使用
C++ 代码
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 505, M = 5555;
int fin[M], val[M], last[N], nxt[M], cnt[N], dist[N], vis[N];
queue<int> forUpdate;
int tot = 2, n, m, w, s, e, t;
void connect(int s, int e, int v)
{
fin[tot] = e;
val[tot] = v;
nxt[tot] = last[s];
last[s] = tot++;
}
//可以将是否存在死锁的true/false直接转换成需求中的YES/NO字符串
string canReturnBeforeStart(int n)
{
//每组数据单独判断
fill(dist, dist + N, 0);
fill(cnt, cnt + N, 0);
//图有可能不是连通的,每个节点出发都有可能遇上死锁
fill(vis, vis + n, 1);
for (int i = 1; i <= n; i++) forUpdate.push(i);
while (!forUpdate.empty())
{
int cur = forUpdate.front();
forUpdate.pop();
vis[cur] = 0;
for (int i = last[cur]; i; i = nxt[i])
{
int ed = fin[i];
if (dist[ed] > dist[cur] + val[i])
{
dist[ed] = dist[cur] + val[i];
cnt[ed] = cnt[cur] + 1;
//更新次数大于n-1就代表存在死锁情况
if (cnt[ed] >= n) return "YES";
if (vis[ed] == 0)
{
vis[ed] = 1;
forUpdate.push(ed);
}
}
}
}
return "NO";
}
int main()
{
int x; cin >> x;
while (x--)
{
tot = 2;
fill(last, last + N, 0);
cin >> n >> m >> w;
for (int i = 0; i < m; i++)
{
cin >> s >> e >> t;
//正常道路是双向的
connect(s, e, t);
connect(e, s, t);
}
for (int i = 0; i < w; i++)
{
cin >> s >> e >> t;
//虫洞是单向的
connect(s, e, -t);
}
cout << canReturnBeforeStart(n) << endl;
}
return 0;
}