【题解】Wormholes（spfa判负环）

题目链接：https://acm.sdtbu.edu.cn/vjudge/contest/view.action?cid=2486#problem/C

题意：给定F个样例，每个样例第一行给定n，m，w。共有n个点，接下来m行双向路径和w行单向路径，单向路径权值为负。问整个图中是否存在负环。
思路：很基础的判断负环的题目，可以用bellman_ford或者spfa，这里选择spfa。

代码：

//#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include
#include
#include
#include

using namespace std;

const int N = 5200, INF = 0x3f3f3f3f, M= 10e9+ 7;
typedef pair PII;
typedef long long ll;

int n, m, w;
int h[N], e[N], ne[N], W[N], idx;
int cnt[N];
int d[N];
int st[N];

void add(int x, int y,int z)
{
	W[idx]=z, e[idx] = y, ne[idx] = h[x], h[x] = idx++;
}

int spfa()
{
	memset(st, 0, sizeof st);
	memset(d, 0, sizeof d);
	memset(cnt, 0, sizeof cnt);

	queueq;
	for (int i = 1; i <= n; ++i)
	{
		q.push(i);
		st[i] = 1;
	}

	while (q.size())
	{
		auto t = q.front();
		q.pop();
		st[t] = 0;

		for (int i = h[t]; i != -1; i = ne[i])
		{
			int j = e[i], c = W[i];
			if (d[j] > d[t] + c)
			{
				d[j] = d[t] + c;
				cnt[j] = cnt[t] + 1;

				if (cnt[j] >= n)return 1;
				
				if (!st[j])
				{
					q.push(j);
					st[j] = 1;
				}
			}
		}
	}

	return 0;
}
int main()
{
	int T;
	cin >> T;

	while (T--)
	{
		memset(h, -1, sizeof h);
		memset(e, 0, sizeof e);
		memset(W, 0, sizeof W);
		memset(ne, 0, sizeof ne);
		idx = 0;

		cin >> n >> m >> w;
		for (int i = 0; i < m; ++i)
		{
			int a, b, c;
			cin >> a >> b >> c;
			add(a, b, c), add(b, a, c);
		}
		for (int i = 0; i < w; ++i)
		{
			int a, b, c;
			cin >> a >> b >> c;
			add(a, b, -c);
		}

		int ans=spfa();
		ans ? cout << "YES" << endl : cout << "NO" << endl;
	}

	return 0;
}

【题解】Wormholes（spfa判负环）

C/C++/C#相关栏目本月热门文章