文章目錄

• • • 題目分析
    • 題目鏈接

題目分析

來源：acwing

分析：

負(fù)環(huán)：負(fù)環(huán)是這樣的一個(gè)環(huán)，該環(huán)上的邊權(quán)之和是負(fù)數(shù)。

存在負(fù)環(huán)的話，會對我們求最短路造成障礙，因?yàn)槔@著這個(gè)負(fù)環(huán)轉(zhuǎn)無數(shù)次，最短路越來越小，最后是－∞。

求負(fù)環(huán)的常見方法， 基于SPFA：

統(tǒng)計(jì)每個(gè)點(diǎn)入隊(duì)的次數(shù)，如果某個(gè)點(diǎn)入隊(duì)n次（說明某點(diǎn)被更新大于等于n次），則說明存在負(fù)環(huán)。

統(tǒng)計(jì)每個(gè)點(diǎn)的最短路中所包含的邊數(shù)，如果某點(diǎn)的最短路所包含的邊數(shù)大于等于n，則說明有負(fù)環(huán)。（常用該法）

SPFA求負(fù)環(huán)的時(shí)間復(fù)雜度，經(jīng)驗(yàn)值是$O(mn)$,所以可能會超時(shí)。這里有個(gè)取巧的方法：當(dāng)所有點(diǎn)的入隊(duì)次數(shù)超過2n(或者3n)時(shí)，我們就認(rèn)為圖中有很大可能是存在負(fù)環(huán)的。

AC代碼

#include<bits/stdc++.h> using namespace std; const int N = 510, M = 5210; int n, m1, m2; int h[N], e[M], w[M], ne[M], idx; int dist[N]; int q[N], cnt[N]; bool st[N];void add(int a, int b, int c){e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++; }// spfa判斷負(fù)環(huán) bool spfa(){int hh = 0, tt = 0;memset(dist, 0, sizeof dist); // 距離可以初始化為任何值memset(st, 0, sizeof st); // 判重?cái)?shù)組memset(cnt, 0, sizeof cnt); // 最短路包含的邊數(shù)// 所有點(diǎn)壓入隊(duì)列，分析過程需要借助虛擬源點(diǎn)for(int i =1; i <= n; i ++){q[tt ++] = i;st[i] = true;}while(hh != tt){auto t = q[hh ++];//循環(huán)隊(duì)列：走到終點(diǎn)，回到開頭if(hh == N) hh = 0; st[t] = false; // 出隊(duì)，標(biāo)記一下for(int i = h[t]; ~i ;i = ne[i]){int j = e[i];if(dist[j] > dist[t] + w[i]){dist[j] = dist[t] + w[i];cnt[j] = cnt[t] + 1;// 以j為終點(diǎn)的最短路的邊數(shù)// 如果邊數(shù)≥n，說明存在負(fù)環(huán)if(cnt[j] >= n) return true;if(!st[j]){q[ tt++] = j;if(tt == N) tt = 0;st[j] = true;}}}}return false; }int main(){int T;cin >> T;while(T --){cin >> n >> m1 >> m2;memset(h, -1, sizeof h);idx = 0;while(m1 --){int a, b, c;cin >> a >> b >> c;add(a, b, c), add(b, a, c);}// 負(fù)權(quán)邊while( m2 --){int a, b, c;cin >> a >> b >> c;add(a, b, -c);}if(spfa()) puts("YES");else puts("NO");}}

題目鏈接

https://www.acwing.com/problem/content/906/

總結(jié)

以上是生活随笔為你收集整理的算法提高课-图论-负环-AcWing 904. 虫洞：spfa求负环裸题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。