P3385 負環
有負權的圖sssp問題不一定無解,但是有負環的圖sssp問題一定無解.
題目描述
給定一張帶負權邊的圖,求從1開始到每個點的最短路路徑上是否有負環. 可能有重邊或者自環.
題目分析
帶負權的圖做最短路,顯然隻能用 s p f a spfa spfa.
spfa這種最短路算法.如果一個環上的邊權有負的,我們可以重複走這條路來獲得更小的邊權,是以這可以作為我們使用spfa判斷負環的根據.
根據 b e l l m a n   f o r d bellman\:ford bellmanford算法,一條兩點間的最短路至多經過n點,也就是說最多進隊松弛 n − 1 n-1 n−1次. 如果一個位置入隊次數不小于n次,那它一定位于環上,是以這可以作為我們的判斷标準.
注意由于可能有自環和重邊,是以我們每搜完一個點,都要立即解除它的标記,否則就會出現因為自環入隊n次而不能判出的情況.
程式實作
#include<bits/stdc++.h>
#define maxn 6010
#define inf 0x3f3f3f3f
using namespace std;
struct edge{
int v,w,next;
}e[maxn];
int head[maxn],tot;
void add(int u,int v,int w){
e[++tot].v =v;
e[tot].w =w;
e[tot].next =head[u];
head[u]=tot;
}
int n,m;
bool vis[maxn];
int dis[maxn],tim[maxn];
bool spfa(){
memset(tim,0,sizeof tim);
memset(vis,false,sizeof vis);
memset(dis,inf,sizeof dis);
queue<int >q;
vis[1]=true;
tim[1]=1;
dis[1]=0;
q.push(1);
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=false;//就是這個地方!要先解除标記
if(tim[u]>=n)return true;
for(int i=head[u];i;i=e[i].next ){
int v=e[i].v ;
if(dis[v]>dis[u]+e[i].w ){
dis[v]=dis[u]+e[i].w ;
if(!vis[v]){//否則負數自環就判不出來了
tim[v]++;
if(tim[v]>=n)return true;
vis[v]=true;
q.push(v);
}
}
}
}
return false;
}
int main(){
int T;
scanf("%d",&T);
for(int ab=1;ab<=T;ab++){
memset(e,0,sizeof e);
memset(head,0,sizeof head);
tot=0;
scanf("%d%d",&n,&m);
for(int i=1,u,v,w;i<=m;i++){
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
if(w>=0)add(v,u,w);
}
bool flag=spfa();
if(flag)printf("YE5\n");
else printf("N0\n");
}
return 0;
}
題後反思
d i j k s t r a dijkstra dijkstra是求不了負權圖上的 s s s p sssp sssp的,也不能求單源最長路徑,隻有 s p f a spfa spfa才行.
是以熟練使用 s p f a spfa spfa是有必要的.