tarjan 可以判负环吗，感觉思路没啥问题，只有20pts

可能代码有点锅，偷偷到机房码的

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+5,M=3e3+5;
int n,m;
struct sd{
	int to,next,val;
}edge[M<<1];
int head[N],tot;
inline void add(int x,int y,int z){
	edge[++tot].next=head[x];
	edge[tot].to=y;
	edge[tot].val=z;
	head[x]=tot;
}
int dfn[N],low[N],cnt;
int scc[N],scc_cnt,scc_val[N];
stack<int> st;
inline void tarjan(int x){
	st.push(x);
	dfn[x]=low[x]=++cnt;
	for(int i=head[x];i;i=edge[i].next){
		int y=edge[i].to;
		if(!dfn[y]){
			tarjan(y);
			low[x]=min(low[x],low[y]);
		}
		else if(!scc[y]) low[x]=min(low[x],dfn[y]);
	}
	if(low[x]==dfn[x]){
		scc[x]=++scc_cnt;
		while(st.top()!=x){
			scc[st.top()]=scc_cnt;
			st.pop();
		}
		st.pop();
	}
}
int f1[M],f2[M],v[M];
inline void init(){
	tot=0;
	cnt=0;
	scc_cnt=0;
	for(int i=1;i<=N;i++) f1[i]=f2[i]=v[i]=scc[i]=scc_val[i]=dfn[i]=head[i]=low[i]=0;
	while(st.size()) st.pop();
}

bool check(){
	for(int i=1;i<=m;i++){
		if(!scc[f1[i]]) continue;
		if(scc[f1[i]]==scc[f2[i]]) scc_val[i]+=v[i];
	}
	for(int i=1;i<=scc_cnt;i++) if(scc_val[i]<0) return 1;
	return 0;
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		init();
		scanf("%d%d",&n,&m);
		for(int i=1;i<=m;i++){
			int a,b,c;
			scanf("%d%d%d",&a,&b,&c);
			f1[i]=a,f2[i]=b,v[i]=c;
			c>=0?add(a,b,c),add(b,a,c):add(a,b,c);
		}
		tarjan(1);
		check()?puts("YES"):puts("NO");
	}
	return 0;
}
```