首页 > 其他分享 >spfa判负环

spfa判负环

时间:2022-11-03 08:58:44浏览次数:87  
标签:10 cnt vis int leq 判负 spfa

模板题

题目描述

给定一个 \(n\) 个点的有向图,请求出图中是否存在从顶点 \(1\) 出发能到达的负环。

负环的定义是:一条边权之和为负数的回路。

输入格式

本题单测试点有多组测试数据

输入的第一行是一个整数 \(T\),表示测试数据的组数。对于每组数据的格式如下:

第一行有两个整数,分别表示图的点数 \(n\) 和接下来给出边信息的条数 \(m\)。

接下来 \(m\) 行,每行三个整数 \(u, v, w\)。

  • 若 \(w \geq 0\),则表示存在一条从 \(u\) 至 \(v\) 边权为 \(w\) 的边,还存在一条从 \(v\) 至 \(u\) 边权为 \(w\) 的边。
  • 若 \(w < 0\),则只表示存在一条从 \(u\) 至 \(v\) 边权为 \(w\) 的边。

输出格式

对于每组数据,输出一行一个字符串,若所求负环存在,则输出 YES,否则输出 NO

样例 #1

样例输入 #1

2
3 4
1 2 2
1 3 4
2 3 1
3 1 -3
3 3
1 2 3
2 3 4
3 1 -8

样例输出 #1

NO
YES

提示

数据规模与约定

对于全部的测试点,保证:

  • \(1 \leq n \leq 2 \times 10^3\),\(1 \leq m \leq 3 \times 10^3\)。
  • \(1 \leq u, v \leq n\),\(-10^4 \leq w \leq 10^4\)。
  • \(1 \leq T \leq 10\)。

提示

请注意,\(m\) 不是图的边数。

code

#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 10;
int n, m;
vector<pair<int, int> > e[N];
int d[N], cnt[N];//cnt[x]表示1-x的最短路包含的边数
bool vis[N];
bool spfa() {
	queue<int> q;
	memset(d, 0x3f, sizeof d);
	memset(vis, 0, sizeof vis);
	memset(cnt, 0, sizeof cnt);
	d[1] = 0, vis[1] = 1;
	q.push(1);
	while (!q.empty()) {
		int x = q.front(); q.pop();
		vis[x] = 0;
		for (int i = 0; i < e[x].size(); i ++) {
			int y = e[x][i].first, z = e[x][i].second;
			if (d[y] > d[x] + z) {
				d[y] = d[x] + z;
				cnt[y] = cnt[x] + 1;//记录最短路径的边数
				if (cnt[y] >= n) return 1;
				//最多n-1条边就包含n个点,边数大等于n,说明有负环 
				if (!vis[y]) {
					q.push(y);
					vis[y] = 1;
				}
			}
		}
	}
	return 0;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int T; cin >> T;
	while (T --) {
		for (int i = 1; i <= N; i ++) e[i].clear();
		cin >> n >> m;
		for (int i = 1; i <= m; i ++) {
			int u, v, w; cin >> u >> v >> w;
			e[u].push_back(make_pair(v, w));
			if (w >= 0) e[v].push_back(make_pair(u, w));
		}
		puts(spfa() ? "YES" : "NO");
	}
	return 0;
}

image

标签:10,cnt,vis,int,leq,判负,spfa
From: https://www.cnblogs.com/YHxo/p/16853211.html

相关文章

  • 洛谷P1462spfa + 二分答案
    第一次接触二分答案的题目最开始是没有思路的看了一个题解,然后强行理解之后开始自己打了一遍,然而结果是只得了30分过了3个点其他全wa,之后是漫长的debug,这里想感慨一句自己d......
  • 【CF553E】Kyoya and Train(期望dp,SPFA,FFT)
    考虑dp。发现正着dp好像不太好做,毕竟初值不太好设,而且时间一大于\(t\)费用就要加上\(x\),所以考虑倒着dp。设\(f_{u,j}\)表示现在已经到达\(u\)点,耗时\(j\),问......
  • spfa和bfs的区别
    \(spfa\)和\(bfs\)的区别\(spfa\)在形式上和\(bfs\)非常类似,不同的是\(bfs\)中一个点出了队列就不可能重新进入队列,但是\(spfa\)中一个点可能在出队列之后再次被放入队列,......
  • POJ 3256(SPFA)
    这题只能对每一个点查一遍……有向图的话能用floyd,可是迫于时限用了SPFA。Programaa;constmaxk=10000;maxn=10000;maxm=10000;vark,n,m,i,j,l:longint;a:ar......
  • Luogu P2656采蘑菇(Tarjan + spfa)
    采蘑菇题目描述小胖和ZYR要去ESQMS森林采蘑菇。ESQMS森林间有\(N\)个小树丛,\(M\)条小径,每条小径都是单向的,连接两个小树丛,上面都有一定数量的蘑菇。小胖和ZYR......
  • T278162 最短路 (spfa+分层图)
    (没穿红色的可莉......)题目描述给定一张\(n\)个点\(m\)条边的连通图,每条边有权值\(w\),定义从\(u_1\)到\(u_x\)经过边\(e_1,e_2,…,e_k\)的路径长度为:请分别......
  • 洛谷 P2387 [NOI2014] 魔法森林 题解【动态加点 SPFA】
    题目大意给定一个由\(n\)个点\(m\)条边的无向图,每条边有权值\((a,b)\),求一条路径使这条路径上的\((a_{\max}+b_{\max})\)最小。思路正解应该是LCT动态维护MST......
  • SPFA算法思想简述
    首先定义数组\(d_i\)表示起点到\(i\)的距离(除起点外初始化为最大值),并维护一个队列。初始将起点入队,然后每一次取队头\(x\)并且松弛所有与\(x\)相连的边,同时如果能......
  • SPFA例题/模板
    https://www.acwing.com/problem/content/1131/ #include<bits/stdc++.h>#definefore(x,y,z)for(LLx=(y);x<=(z);x++)#defineforn(x,y,z)for(LLx=(y);x<(z);......
  • 缩点后 spfa求最长路(不知道为什么top+dp做不了)
    #include<queue>#include<cstdio>#include<cstring>#defineN500005usingnamespacestd;structedge{intto,val,next;}e[N];intm,n,p,s,cnt,g[N],u[N],v......