Znzryb's Blog
0%

Posted on Edited on

思路讲解

AC代码

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

Posted on Edited on

思路讲解

01染色问题

AC代码

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

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
// Problem: P1330 封锁阳光大学
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1330
// Memory Limit: 125 MB
// Time Limit: 1000 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>(1e6)+10,INF=static_cast<ll>(5e18)+3;

ll N,M,T,A[MAXN];
vector<ll> g[MAXN];
ll color[MAXN];
ll sum=0;
ll cnt=0;
bool abNormal=false;

void dfs(ll x,ll xcolor){
	if(abNormal) return;
	if(color[x]!=0 && color[x]!=xcolor){
		abNormal=true;
		return;
	}else if(color[x]!=0){
		return;
	}
	color[x]=xcolor;
	sum+=1;
	if(xcolor==2) cnt+=1;
	for(int i=0;i<g[x].size();++i){
		ll v=g[x][i];
		dfs(v,3-xcolor);
	}
}

inline void solve(){
	cin>>N>>M;
	FOR(i,1,M){
		ll u,v;
		cin>>u>>v;
		g[u].pb(v);
		g[v].pb(u);
	}
	ll ans=0;
	FOR(i,1,N){
		if(color[i]!=0) continue;
		sum=0;
		cnt=0;
		abNormal=false;
		dfs(i,1);
		if(abNormal){
			cout<<"Impossible\n";
			return;
		}
		if(cnt>sum-cnt){
			ans+=sum-cnt;
		}else{
			ans+=cnt;
		}
	}
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>T;
	// while(T--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC
https://www.luogu.com.cn/record/210621292
*/

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

Posted on Edited on

思路讲解

这道题目的图论建模还是很有启发意义的。

如果你发现两个值要不一样，这个就说明他们属于不同的集合。

如果你发现两个值要一样，这个就说明他们属于相同的集合。

按位分析建图，配合dsu解决问题

https://www.luogu.com.cn/problem/P1330 然后01染色，类似于这道题目

P1330 封锁阳光大学

AC代码

1

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

还是调了比较久的

从低位到高位写已经相当于反过来了（一般数字都是从高位到低位写），不需要用栈再反一次，可以用队列，相当于没反

1
2
3
4
5
6
7
8
9
10
11
12
13
FOR(i,1,M){
	ll z=xyz[i][2];
	deque<ll> bits;
	while(z){
		bits.pb(z%2);
		z/=2;
	}
	ll idx=0;
	while(!bits.empty()){
		bitZ[i][++idx]=bits.front();
		bits.pop_front();
	}
}

https://atcoder.jp/contests/abc396/submissions/64227463

这个主要问题在于实现思路有瑕疵

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
// Problem: E - Min of Restricted Sum
// Contest: AtCoder - AtCoder Beginner Contest 396
// URL: https://atcoder.jp/contests/abc396/tasks/abc396_e
// Memory Limit: 1024 MB
// Time Limit: 3000 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>(2e5)+10,INF=static_cast<ll>(5e18)+3;

ll N,M,T,A[MAXN];
arr xyz[MAXN];
ll bitZ[MAXN][35];
ll fa[MAXN][35];
ll pow2[35];
vector<ll> rootDiff[MAXN][35],diffXY[MAXN][35];
ll rootCnt[MAXN][35];
ll limit=0;
ll ans=0;
bool vis[MAXN][35];
bool needAdd[MAXN][35];

ll find(ll lay,ll x){
	if(fa[x][lay]==x) return x;
	return fa[x][lay]=find(lay,fa[x][lay]);
}
void merge(ll lay,ll x,ll y){
	fa[x][lay]=find(lay,y);
	rootCnt[y][lay]+=rootCnt[x][lay];
}

void dfs(ll lay,ll x,ll color,vector<ll> &vis0,vector<ll> &vis1){
	if(vis[x][lay]) return;
	vis[x][lay]=true;
	if(color==1) vis1.pb(x),ans+=rootCnt[x][lay];
	else vis0.pb(x);
	FOR(i,0,SZ(rootDiff[x][lay])-1){
		ll v=rootDiff[x][lay][i];
		if(vis[v][lay]) continue;
		dfs(lay,v,1-color,vis0,vis1);
	}
}

inline void solve(){
	cin>>N>>M;
	FOR(i,1,M){
		cin>>xyz[i][0]>>xyz[i][1]>>xyz[i][2];
	}
	limit=ceil(log(N)/log(2))+1;
	FOR(i,1,N){
		FOR(j,1,limit){
			fa[i][j]=i;
			rootCnt[i][j]=1;
		}
	}
	FOR(i,1,M){
		ll z=xyz[i][2];
		deque<ll> bits;
		while(z){
			bits.pb(z%2);
			z/=2;
		}
		ll idx=0;
		while(!bits.empty()){
			bitZ[i][++idx]=bits.front();
			bits.pop_front();
		}
	}
	FOR(j,1,limit){
		FOR(i,1,M){
			ll x=xyz[i][0],y=xyz[i][1];
			if(bitZ[i][j]==0){
				merge(j,x,y);
			}
		}
		FOR(i,1,M){
			ll x=xyz[i][0],y=xyz[i][1];
			if(bitZ[i][j]==1){
				// 该条件与前面的要求冲突了，直接输出-1
				if(find(j,x)==find(j,y) && x!=y){
					cout<<-1<<"\n";
					return;
				}else{
					diffXY[x][j].pb(y);
					diffXY[y][j].pb(x);
				}
			}
		}
	}
	
#ifdef LOCAL
    cerr << "OK1" << '\n';
#endif

	FOR(i,1,N){
		FOR(j,1,limit){
			FOR(k,0,SZ(diffXY[i][j])-1){
				ll fai=find(j,i),fax=find(j,diffXY[i][j][k]);
				rootDiff[fai][j].pb(fax);
			}
		}
	}
	
	// 去重
	FOR(i,1,N){
		FOR(j,1,limit){
			sort(all(rootDiff[i][j]));
			rootDiff[i][j].resize(unique(all(rootDiff[i][j]))-rootDiff[i][j].begin());
		}
	}
#ifdef LOCAL
    cerr << "OK2" << '\n';
    FOR(i,1,N){
		FOR(j,1,limit){
			if(rootDiff[i][j].empty()) continue;
			cerr<<i<<": ";
			FOR(k,0,SZ(rootDiff[i][j])-1){
				cerr<<rootDiff[i][j][k]<<" ";
			}
			cerr<<"\n";
		}
	}
#endif

	// 然后对每层01染色就行了
	FOR(i,1,limit){
		FOR(j,1,N){
			ll faj=find(i,j);
			if(vis[faj][i]) continue;
			vector<ll> vis0,vis1,vis00,vis11;
			ans=0;
			dfs(i,faj,0,vis0,vis1);
// #ifdef LOCAL
    // cerr << "OK--"<< i<<" "<<j << '\n';
// #endif
			FOR(k,0,SZ(vis0)-1){
				vis[vis0[k]][i]=false;
			}
			FOR(k,0,SZ(vis1)-1){
				vis[vis1[k]][i]=false;
			}
			ll lans=ans;
			ans=0;
			dfs(i,faj,1,vis00,vis11);
#ifdef LOCAL
	cerr<<"vis11: ";
    for(int k=0;k<vis11.size();++k){
    	cerr<<vis11[k]<<" ";
    }
    cerr<<"\n";
    cerr<<"vis1: ";
    for(int k=0;k<vis1.size();++k){
    	cerr<<vis1[k]<<" ";
    }
    cerr<<"\n";
#endif
			if(lans<ans){
				FOR(k,0,SZ(vis1)-1){
					needAdd[vis1[k]][i]=true;
				}
			}else{
				FOR(k,0,SZ(vis11)-1){
					needAdd[vis11[k]][i]=true;
				}
			}
		}
	}
// #ifdef LOCAL
    // cerr << "OK3" << '\n';
// #endif
	FOR(i,1,limit){
		FOR(j,1,N){
			ll faj=find(i,j);
			if(needAdd[faj][i]){
				A[j]+=pow2[i];
			}
		}
	}
	
	FOR(i,1,M){
		// 免去我们无向图判偶数环，直接校验我们的答案正确性
		ll x=xyz[i][0],y=xyz[i][1],z=xyz[i][2];
		if((A[x]^A[y])!=z){
			cout<<-1<<"\n";
			return;
		}
	}
	FOR(i,1,N){
		cout<<A[i]<<" ";
	}
	cout<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>T;
	// while(T--){
		// solve();
	// }
	pow2[1]=1;	// 采用的是1-based
	FOR(i,2,33){
		pow2[i]=pow2[i-1]*2;
	}
	solve();
	return 0;
}
/*
WA https://atcoder.jp/contests/abc396/submissions/64227025

*/

还没有查出来哪里有问题

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
// Problem: E - Min of Restricted Sum
// Contest: AtCoder - AtCoder Beginner Contest 396
// URL: https://atcoder.jp/contests/abc396/tasks/abc396_e
// Memory Limit: 1024 MB
// Time Limit: 3000 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>(2e5)+10,INF=static_cast<ll>(5e18)+3;

ll N,M,T,A[MAXN];
arr xyz[MAXN];
ll bitZ[MAXN][35];
ll fa[MAXN][35];
ll pow2[35];
vector<ll> rootDiff[MAXN][35],diffXY[MAXN][35];
ll rootCnt[MAXN][35];
ll limit=0;
ll ans=0;
ll sum=0;
ll vis[MAXN][35];
bool needAdd[MAXN][35];
bool abNormal=false;

ll find(ll lay,ll x){
	if(fa[x][lay]==x) return x;
	return fa[x][lay]=find(lay,fa[x][lay]);
}
void merge(ll lay,ll x,ll y){
	ll fax=find(lay,x),fay=find(lay,y);
	fa[fax][lay]=fay;
	rootCnt[fay][lay]+=rootCnt[fax][lay];
}

void dfs(ll lay,ll x,ll color,vector<ll> &vis0,vector<ll> &vis1){
	if(abNormal) return;
	if(vis[x][lay]!=0 && vis[x][lay]!=color){
		abNormal=true;
		return;
	}else if(vis[x][lay]!=0){
		return;
	}
	vis[x][lay]=color;
	if(color==2) vis1.pb(x),ans+=rootCnt[x][lay],sum+=rootCnt[x][lay];
	else vis0.pb(x),sum+=rootCnt[x][lay];
	FOR(i,0,SZ(rootDiff[x][lay])-1){
		ll v=rootDiff[x][lay][i];
		if(vis[v][lay]) continue;
		dfs(lay,v,3-color,vis0,vis1);
	}
}

inline void solve(){
	cin>>N>>M;
	FOR(i,1,M){
		cin>>xyz[i][0]>>xyz[i][1]>>xyz[i][2];
	}
	limit=ceil(log(N)/log(2))+1;
	FOR(i,1,N){
		FOR(j,1,limit){
			fa[i][j]=i;
			rootCnt[i][j]=1;
		}
	}
	FOR(i,1,M){
		ll z=xyz[i][2];
		deque<ll> bits;
		while(z){
			bits.pb(z%2);
			z/=2;
		}
		ll idx=0;
		while(!bits.empty()){
			bitZ[i][++idx]=bits.front();
			bits.pop_front();
		}
	}
	
#ifdef LOCAL	// bitZ 没有问题
    FOR(i,1,M){
    	cerr<<xyz[i][0]<<" "<<xyz[i][1]<<" "<<xyz[i][2]<<": ";
    	FOR(lay,1,limit){
    		cerr<<bitZ[i][lay]<<" ";
    	}
    	cerr<<"\n";
    }
#endif

	FOR(j,1,limit){
		FOR(i,1,M){
			ll x=xyz[i][0],y=xyz[i][1];
			if(bitZ[i][j]==0){
				merge(j,x,y);
			}
		}
		FOR(i,1,M){
			ll x=xyz[i][0],y=xyz[i][1];
			if(bitZ[i][j]==1){
				// 该条件与前面的要求冲突了，直接输出-1
				if(find(j,x)==find(j,y) && x!=y){
					cout<<-1<<"\n";
					return;
				}else{
					diffXY[x][j].pb(y);
					diffXY[y][j].pb(x);
				}
			}
		}
	}
	
// #ifdef LOCAL
    // cerr << "OK1" << '\n';
// #endif

	FOR(i,1,N){
		FOR(j,1,limit){
			FOR(k,0,SZ(diffXY[i][j])-1){
				ll fai=find(j,i),fax=find(j,diffXY[i][j][k]);
				rootDiff[fai][j].pb(fax);
			}
		}
	}
	
	// 去重
	FOR(i,1,N){
		FOR(j,1,limit){
			sort(all(rootDiff[i][j]));
			rootDiff[i][j].resize(unique(all(rootDiff[i][j]))-rootDiff[i][j].begin());
#ifdef LOCAL
	cerr<<"lay: "<<j<<" node:"<<i<<"/ ";
    for(int k=0;k<rootDiff[i][j].size();++k){
    	cerr<<rootDiff[i][j][k]<<" ";
    }
    cerr<<"\n";
#endif
		}
	}

	// 然后对每层01染色就行了
	FOR(i,1,limit){
		FOR(j,1,N){
			ll faj=find(i,j);
			if(vis[faj][i]!=0) continue;
			vector<ll> vis0,vis1;
			ans=0;
			sum=0;
			abNormal=false;
			dfs(i,faj,1,vis0,vis1);
			if(abNormal){
				cout<<-1<<"\n";
				return;
			}
			if(ans<sum-ans){
				FOR(k,0,SZ(vis1)-1){
					needAdd[vis1[k]][i]=true;
				}
			}else{
				FOR(k,0,SZ(vis0)-1){
					needAdd[vis0[k]][i]=true;
				}
			}
		}
	}

	FOR(i,1,limit){
		FOR(j,1,N){
			ll faj=find(i,j);
			if(needAdd[faj][i]){
				A[j]+=pow2[i];
			}
		}
	}
	
	FOR(i,1,M){
		// 免去我们无向图判偶数环，直接校验我们的答案正确性
		ll x=xyz[i][0],y=xyz[i][1],z=xyz[i][2];
		if((A[x]^A[y])!=z){
			cout<<-1<<"\n";
			return;
		}
	}
	FOR(i,1,N){
		cout<<A[i]<<" ";
	}
	cout<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	pow2[1]=1;	// 采用的是1-based
	FOR(i,2,33){
		pow2[i]=pow2[i-1]*2;
	}
	solve();
	return 0;
}
/*
WA https://atcoder.jp/contests/abc396/submissions/64227025
0 8 13 4 0 1 13 0 0 0 2 0 0 0 0 

15 6
3 10 13
2 7 5
5 4 4
11 7 15
5 7 13
15 6 1

ans:
0 8 0 4 0 0 13 0 0 13 2 0 0 0 1
*/

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
*/

Posted on Edited on

思路讲解

这题的关键在于K站中转站内。

通过clone数组备份，确保每次松弛只松弛一次，不会连续松弛，确保不超出题设要求。

AC代码

https://leetcode.cn/problems/cheapest-flights-within-k-stops/submissions/615024531

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        const int INF=static_cast<int>(1e9)+7;
        vector<int> dist(n+5,INF);
        dist[src]=0;
        for(int limit=0;limit<=k;++limit){
            vector<int> clone(dist.begin(),dist.end());
            for(int i=0;i<flights.size();++i){
                int u=flights[i][0],v=flights[i][1],price=flights[i][2];
                if(dist[v]>clone[u]+price){
                    dist[v]=clone[u]+price;
                }
            }
        }
        return (dist[dst]==INF?-1:dist[dst]);
    }
};

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