Znzryb's Blog
0%

P3385 【模板】负环

Posted on Edited on

思路讲解

我实际上是用bellman-ford算法搞的。

那么如果松弛n次都没有松弛下来，就说明一定有负环，因为正常的最短路不会经过一个点多次。

AC代码

https://www.luogu.com.cn/record/210047386

其实也没有什么做不了的，如果dist[j]==INF，那么说明1点还没有到达过你这个点，那么就说明不能进行松弛操作，避免被hack

1
2
3
4
5
6
7
8
1
4 3 
2 3 -1
3 4 -1
4 2 -1

NO

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
// Problem: P3385 【模板】负环
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3385
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(2e3)+10,INF=static_cast<ll>(5e18)+3;

ll N,M,T,A[MAXN];

inline void solve(){
	cin>>N>>M;
	vector<ll> dist(N+5,INF);
	vector<vector<pll>> g(N+5);
	FOR(i,1,M){
		ll u,v,w;
		cin>>u>>v>>w;
		g[u].pb({v,w});
		if(w>=0){
			g[v].pb({u,w});
		}
	}
	dist[1]=0;
	FOR(i,1,N+5){
		bool flag=false;
		FOR(j,1,N){
			FOR(k,0,SZ(g[j])-1){
				ll node=g[j][k].fi,w=g[j][k].se;
				if(dist[node]>dist[j]+w && dist[j]!=INF){
					dist[node]=dist[j]+w;
					flag=true;
				}
			}
		}
		if(flag==false){
			cout<<"NO\n";
			return;
		}
	}
	cout<<"YES\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}
/*

https://www.luogu.com.cn/record/210043824
*/

心路历程（WA，TLE，MLE……）

这个下面的代码用来判断负环是没有问题的，问题在于bellman-ford算法无法判断是不是能从1到达这个负环。

https://www.luogu.com.cn/record/210044531

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
// Problem: P3385 【模板】负环
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3385
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(2e3)+10,INF=static_cast<ll>(5e18)+3;

ll N,M,T,A[MAXN];

inline void solve(){
	cin>>N>>M;
	vector<ll> dist(N+5,INF);
	vector<vector<pll>> g(N+5);
	FOR(i,1,M){
		ll u,v,w;
		cin>>u>>v>>w;
		g[u].pb({v,w});
		if(w>=0){
			g[v].pb({u,w});
		}
	}
	dist[1]=0;
	FOR(i,1,N+5){
		bool flag=false;
		FOR(j,1,N){
			FOR(k,0,SZ(g[j])-1){
				ll node=g[j][k].fi,w=g[j][k].se;
				if(dist[node]>dist[j]+w){
					dist[node]=dist[j]+w;
					flag=true;
				}
			}
		}
		if(flag==false){
			cout<<"NO\n";
			return;
		}
	}
	cout<<"YES\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}
/*

https://www.luogu.com.cn/record/210043824
*/