对于每个$(x,y,w)$，连边$(x-1,y,w),(y,x-1,-w)$，表示前$y$个月的收益比前$x-1$个月的收益大$w$
这样题目就转化为询问图中是否有非零环存在
于是我们找找正环（最长路）和负环（最短路）就好了
#include<iostream> #include<cstdio> #include<cstring> using namespace std; #define N 105 int T,n,m,a[N][N],f1[N],f2[N],inf; bool vis1[N],vis2[N],ok; void spfa1(int x){ if(vis1[x]) ok=1; if(ok) return ; vis1[x]=1; for(int i=0;i<=n&&!ok;++i) if(a[x][i]!=inf) if(f1[i]>f1[x]+a[x][i]) f1[i]=f1[x]+a[x][i],spfa1(i); vis1[x]=0; } void spfa2(int x){ if(vis2[x]) ok=1; if(ok) return ; vis2[x]=1; for(int i=0;i<=n&&!ok;++i) if(a[x][i]!=inf) if(f2[i]<f2[x]+a[x][i]) f2[i]=f2[x]+a[x][i],spfa2(i); vis2[x]=0; } int main(){ scanf("%d",&T); while(T--){ memset(a,127,sizeof(a)); inf=a[0][0]; memset(f1,127,sizeof(f1)); memset(f2,128,sizeof(f2)); scanf("%d%d",&n,&m); ok=0; f1[0]=f2[0]=0; for(int i=1,u,v,w;i<=m;++i){ scanf("%d%d%d",&u,&v,&w); a[u-1][v]=w; a[v][u-1]=-w; } for(int i=0;i<=n;++i) spfa1(i),spfa2(i); puts(ok?"false":"true"); }return 0; }