题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1202
据说这道题可以用并查集来做，但是太神奇我太弱不会，就只能水水的用差分约束水过去了。
令账目的前缀和为pre[]，那么对于每一个信息pre[t]-pre[s-1]=v
即pre[t]-pre[s-1]<=v&&pre[t]-pre[s-1]>=v，然后就SPFA来搞差分约束就可以拉。
代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <stack>
using namespace std ;
#define MAXN 110
struct edge {
edge *next ;
int t , d ;
} *head[ MAXN ] ;
void AddEdge( int s , int t , int d ) {
edge *p = new( edge ) ;
p -> t = t , p -> d = d , p -> next = head[ s ] ;
head[ s ] = p ;
}
int n , m , w ;
stack < int > S ;
int dist[ MAXN ] , cnt[ MAXN ] ;
bool f[ MAXN ] ;
bool spfa( ) {
while ( ! S.empty( ) ) S.pop( ) ;
for ( int i = 0 ; i <= n ; i ++ ) dist[ i ] = 0 , cnt[ i ] = 1 , S.push( i ) ;
memset( f , true , sizeof( f ) ) ;
while ( ! S.empty( ) ) {
int v = S.top( ) ; S.pop( ) , f[ v ] = false ;
for ( edge *p = head[ v ] ; p ; p = p -> next ) if ( dist[ p -> t ] > dist[ v ] + p -> d ) {
if ( ( ++ cnt[ p -> t ] ) > n + 1 ) return false ;
dist[ p -> t ] = dist[ v ] + p -> d ;
if ( ! f[ p -> t ] ) f[ p -> t ] = true , S.push( p -> t ) ;
}
}
return true ;
}
int main( ) {
scanf( "%d" , &w ) ;
while ( w -- ) {
memset( head , 0 , sizeof( head ) ) ;
scanf( "%d%d" , &n , &m ) ;
while ( m -- ) {
int s , t , v ; scanf( "%d%d%d" , &s , &t , &v ) ;
AddEdge( s - 1 , t , v ) , AddEdge( t , s - 1 , - v ) ;
}
printf( spfa( ) ? "true\n" : "false\n" ) ;
}
return 0 ;
}
