[Acwing] 904. 虫洞 Spfa判断负环

前言

spfa 裸题 ;…; 传送门 :

题目分析

给你一个无向图,然后给你几条单向负权边,问你是否可以从自己 更新到自己

(这不就是负环吗？)

Spfa负环

两种方法 (这里使用第二种):

• 统计某个点的入队次数,如果某个点入队 n 次,那么存在负环
• 统计当前每个点的最短路中,所包含的边数,如果某个点的最短路所包含的边数 > = n >=n >=n

两个疑问 :

• 为什么可以把所有点都给直接加进队列 因为建立虚拟源点跑的话,图中有负环的话,那么我们还是会走到负环的
• 为什么 d i s t dist dist 不初始化为 0 x 3 f 0x3f 0x3f 因为在负环转圈的过程中,我们最后会得到一个 − ∞ -∞ −∞,因此没必要0x3f ,只要相同就行

CODE

#include 
using namespace std;
#define ll long long
#define endl '\n'
#define px first
#define py second
#define pb push_back

const int N  = 510;
struct node
{
	int to,val;
};

vector g[N];
int dist[N],cnt[N];
int st[N];

int n,m1,m2;

void spfa()
{
	memset(dist,0,sizeof dist);
	memset(cnt,0,sizeof cnt);
	memset(st,0,sizeof st);

	queue q;
	/**
	判断负环 可以直接把所有点都加进去
	因为不管从哪开始,如果有负环那么一定会走进去
	**/
	for(int i=1;i dist[t]+x.val)
			{
				dist[x.to] = dist[t]+x.val;
				cnt[x.to] = cnt[t]+1;

				if(cnt[x.to] >=n)
                {
                    coutb>>c;
		g[a].pb({b,c});
		g[b].pb({a,c});
	}

	for(int i= 0;i>a>>b>>c;
		g[a].pb({b,-c});
	}

	spfa();
}

int main()
{
    ios::sync_with_stdio(false);
    int t;cin>>t;while(t -- )
    solve();
    return 0;
}