Steven_MengのBlog

传送门

考虑将$s-1$向$t$连一条长度为$v$的边,$t$向$s-1$连一条长度为$-v$的边

先画图分析一下,发现出现如图这样的环,且环上的数之和不为$0$,就是不合法的。

发现如果这样一个环上面的边权之和为正,我们把这样的环上面的所有边取反,就可以得到一个负环。

如果边权之和为负,那么它就是负环。

于是$\rm SPFA$判断图中是否有负环即可

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
// luogu-judger-enable-o2
#include <bits/stdc++.h>
#define MAXN 105
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x*10)+(ch-'0');
ch=getchar();
}
return x*f;
}
struct node{
int to,len;
};
vector<node>G[MAXN];
int in[MAXN];
void AddEdge(int u,int v,int len){
node temp;
temp.to=v;
temp.len=len;
G[u].push_back(temp);
}
int vis[MAXN],dis[MAXN];
int cnt[MAXN];
int n,m;
inline int SPFA(){
queue<int>Q;
for (register int i=0;i<=n;++i){
if (in[i]==0){
vis[i]=1;
dis[i]=0;
Q.push(i);
}
}
while (Q.size()){
int u=Q.front();
Q.pop();
vis[u]=false;
if (++cnt[u]==n){
return false;
}
if (!vis[u]){
for (register int i=0;i<G[u].size();++i){
int v=G[u][i].to;
int len=G[u][i].len;
if (dis[v]>dis[u]+len){
dis[v]=dis[u]+len;
if (!vis[v]){
vis[v]=true;
Q.push(v);
}
}
}
}
}
return true;
}
inline void Init(){
for (register int i=0;i<MAXN;++i){
G[i].clear();
}
memset(vis,0,sizeof(vis));
memset(cnt,0,sizeof(cnt));
memset(dis,0x3f,sizeof(dis));
}
int main(){
int w=read();
while (w--){
Init();
n=read(),m=read();
while (m--){
int l=read(),r=read(),len=read();
AddEdge(l-1,r,len);
AddEdge(r,l-1,-len);
in[r]++;
}
puts(SPFA()?"true":"false");
}
}

 评论