Steven_Meng's Blog

传送门

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

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

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

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

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

// 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");
	}
}