[HNOI2005]狡猾的商人
u→v=c可以理解为sumv−sumu−1=c （前缀和）
定的sumu→v=c 不仅需要满足sumv−sumu−1=c，还应该满足sumu−1−sumv=−c。
接下来就是判断是否存在环(判环)
对于不一定联通的图，每个入度为0的点都要判断，这里是判断toti == 0的点，toti就是i结点访问次数。
数据量小，判断大于n可过，否则要dfs跑spfa
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
#define INF 0x7fffffff
struct Edge{
int v,w,nxt;
};
int cnt,head[100000];
Edge edge[100000];
int book[10005],dis[10005],tot[100005],vis[100005],n,m;
int read(){
int x=0,dign=1;
char c = getchar();
while(c<'0'||c>'9'){
if(c=='-')dign=-1;
c = getchar();
}
while(c>='0'&&c<='9'){
x = x*10 c - '0';
c = getchar();
}
return x*dign;
}
void add(int u,int v,int w){
cnt ;
edge[cnt].v = v; edge[cnt].w = w;
edge[cnt].nxt = head[u];
head[u] = cnt;
}
bool spfa(int u){
queue<int> q;
for(int i=1;i<=n;i )dis[i] = INF;
dis[u] = 0; book[u] = 1; q.push(u);
while(!q.empty()){
int u = q.front(); book[u] = 0; q.pop();
tot[u] ; if(tot[u]==n)return false;
for(int v,w,i = head[u];i;i=edge[i].nxt){
v = edge[i].v; w = dis[u] edge[i].w;
if(dis[v]>w){
dis[v] = w;
if(!book[v]){
book[v]=1; q.push(v);
}
}
}
}
return true;
}
int main()
{
int w;
w = read();
while(w--){
cnt = 0; memset(book,0,sizeof(book));
memset(tot,0,sizeof(tot));
memset(head,0,sizeof(head));
n = read(); m = read();
for(int i=0;i<m;i ){
int a,b,c;
a = read(); b = read(); c = read();
add(a-1,b,c);
add(b,a-1,-c);
}
int f = 1;
for(int i=0;i<=n;i ){
if(!tot[i]){
f = spfa(i);if(!f)break;
}
}
if(!f)printf("falsen");
else printf("truen");
}
return 0;
} 
