表质疑，一个dfs就可以了。首先该题是个判定性问题。又因为这道题有点像查分约束，应该可以证明如果存在的话方案数应该是无穷的（凭蒟蒻的感觉）。而且可以任意指定一个点的值的大小，判断其他的值是否满足。实现起来有点像TWO-SAT。大概就这样。加油！有时间的话还要再回来想一下。
想了一下如果要求输出一个方案的话，还要跑有上下限的网络流，具体是S集点 i 往T集点 j 连上下限均为V（i，j）的边。
1 #include<cstdio> 2 #include<iostream> 3 #define rep(i,j,k) for(register int i = j; i <= k; i++) 4 #define ez(i,j) for(edge*i = head[j]; i; i=i->next) 5 #define maxn 1005 6 using namespace std; 7 8 inline int read() { 9 int s = 0, t = 1; char c = getchar(); 10 while( !isdigit(c) ) { if( c == ‘-‘ ) t = -1; c = getchar(); } 11 while( isdigit(c) ) s = s * 10 + c - 48, c = getchar(); 12 return s * t; 13 } 14 15 struct edge{ int to, v; edge*next; } e[maxn<<1], *pt = e, *head[maxn<<1]; 16 inline void add(int x,int y,int v) { pt->to = y, pt->next = head[x], pt->v = v, head[x] = pt++; pt->to = x, pt->v = v, pt->next = head[y], head[y] = pt++; } 17 int d[maxn<<1]; bool flag, vis[maxn<<1]; 18 #define to i->to 19 inline void dfs(int x,int nv) { 20 d[x] = nv; vis[x] = 1; 21 ez(i,x) { 22 if( vis[to] ) { if( d[to] != i->v - nv ) { flag = 0; break; } continue; } 23 else dfs(to,i->v-nv); 24 } 25 } 26 27 int main() { 28 int n, m, k, x, y, v, t = read(); 29 while( t-- ) { 30 n = read(), m = read(), k = read(); 31 rep(i,1,n+m) vis[i] = d[i] = 0, head[i] = 0; pt = e; 32 rep(i,1,k) x = read(), y = read() + n, v = read(), add(x,y,v); 33 flag = 1; 34 rep(i,1,n+m) { 35 if( !vis[i] ) dfs(i,0); 36 if( !flag ) break; 37 } 38 if( flag ) puts("Yes"); else puts("No"); 39 } 40 return 0; 41 }
原文：http://www.cnblogs.com/83131yyl/p/5459872.html