图论-SPFA模板

测试题目：NKOJ1120 NKOJ3639

最常见的 BFS 实现

 1 #include <stdio.h>
 2 #include <queue>
 3 #include <vector>
 4 
 5 typedef long long LL;
 6 
 7 using namespace std;
 8 
 9 const int _N = 420000;
10 const LL INF = 99999999999999LL;
11 
12 
13 LL n, m;
14 LL dis[_N];
15 bool book[_N];
16 
17 struct node {
18     LL v, w;
19     node(LL _v, LL _w):
20         v(_v), w(_w) {}
21 };
22 
23 queue<LL> Q;
24 vector<node> G[_N];
25 
26 void SPFA(LL beg)
27 {
28     LL i, p;
29     for (i = 1; i <= n; ++i)
30         dis[i] = INF, book[i] = false;
31     dis[beg] = 0, Q.push(beg), book[beg] = true;
32     while (!Q.empty()) {
33         int p = Q.front();
34         Q.pop(), book[p] = false;
35         vector<node>::iterator it;
36         for (it = G[p].begin(); it != G[p].end(); ++it) {
37             if (dis[it->v] <= dis[p] + it->w) continue;
38             dis[it->v] = dis[p] + it->w;
39             if (book[it->v]) continue;
40             Q.push(it->v), book[it->v] = true;
41         }
42     }
43     return ;
44 }
45 
46 int main()
47 {
48     LL i, t1, t2, t3;
49     scanf("%lld%lld", &n, &m);
50     for (i = 1; i <= m; ++i) {
51         scanf("%lld%lld%lld", &t1, &t2, &t3);
52         G[t1].push_back(node(t2, t3));
53     }
54     scanf("%lld%lld", &t1, &t2);
55     SPFA(t1);
56     printf("%lld
", dis[t2]);
57     return 0;
58 }

View Code

判负环

BFS 判负环

如果某点入队次数 > N(总点数) ，则存在负环。否则不存在。

DFS 判负环

1.朴素的 DFS 判负环

 1 bool SPFA(int p)
 2 {
 3     bool flag = false;
 4     mk[p] = true;
 5     for (int i = G[p].size()-1; i >= 0; --i) {
 6         edge v = G[p][i];
 7         if (dis[v.v] > dis[p]+v.w) {
 8             dis[v.v] = dis[p]+v.w;
 9             if (!mk[v.v]) {
10                 if (SPFA(v.v)) { flag = true; break; }
11             } else {
12                 flag = true;
13                 break;
14             }
15         }
16     }
17     mk[p] = false;
18     return flag;
19 }

从假设的原点（即假设的到某个点都有一条边的点）开始跑一次 SPFA 。注意先初始化 dis[i] = INF, dis[beg] = 0.

2.优化的 DFS 判负环

SPFA 部分代码同上。设置 dis[i] = 0，这样在 SPFA 过程中总是会选择负权边，提高了效率。然后从每个点开始跑 SPFA ，直到负环出现。

***优化

1.SLF(Small Label First) 当 i 入队时，如果 dis[i] < dis[Q.front()] 则加入队首，否则加入队尾。

2.LLL(Large Label Last) 当准备从队列中取出一个数讨论时，设 ave 为队列中 dis 平均值，如果 dis[Q.front()] > x ，就把队首的元素放到队尾，再次判断是否 dis[Q.front()] > x …… 直到 dis[Q.front()] <= x 。