【luogu P3385 负环】 模板

题目链接：https://www.luogu.org/problemnew/show/P3385

SPFA判负环。

这个题必须卡一卡才过得去。

按理说对于一个负环点应当是入队 > n次。

但是这个题数据不是很友好qwq

所以我们把入队次数变成 >= (n/4)次。

到考试的时候你说是写 > n 还是 > (n/4) ？

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn = 10000 + 10;

const int inf = 0x7fffffff;

struct edge{

	int from, to, next, len;

}e[maxn<<2];

int head[maxn], cnt, visnum[maxn], dis[maxn];

int vis[maxn];

queue<int> q;

int T, n, m;

void add(int u, int v, int w)

{

	e[++cnt].from = u;

	e[cnt].len = w;

	e[cnt].next = head[u];

	e[cnt].to = v;

	head[u] = cnt;

}

bool SPFA()

{

	while(!q.empty())

	{

		int now = q.front();q.pop();

		vis[now] = 0;

		for(int i = head[now]; i != -1; i = e[i].next)

		{

			if(dis[e[i].to] > dis[now] + e[i].len)

			{

				dis[e[i].to] = dis[now] + e[i].len;

				if(!vis[e[i].to])

				{

					visnum[e[i].to]++;

					if(visnum[e[i].to] >= (n>>2)) return 1;

					q.push(e[i].to);

				}

			}

		}

	}

	return 0;

}

int main()

{

	scanf("%d",&T);

	while(T--)

	{

		scanf("%d%d",&n,&m);

		cnt = 0;

		while(!q.empty()) q.pop();

		memset(visnum,0,sizeof(visnum));

		memset(head,-1,sizeof(head));

		memset(vis,0,sizeof(vis));

		memset(e,0,sizeof(e));

		for(int i = 1; i <= n; i++) dis[i] = inf;

		for(int i = 1; i <= m; i++)

		{

			int u, v, w;

			scanf("%d%d%d",&u,&v,&w);

			if(w >= 0)

			{

				add(u, v, w); add(v, u, w);

			}

			if(w < 0)

			{

				add(u, v, w);

			}

		}

		int s = 1;

		q.push(s); dis[s] = 0; vis[s] = 1;

		if(SPFA())

		printf("YE5\n");

		else

		printf("N0\n");

	}

	return 0;

}