bzoj 1202: [HNOI2005]狡猾的商人

可以假设一个A数组为第i天之前的收入，即前缀和。

每次输入的s，t，v即At - As-1 = v。

对，就是一个差分约束。

实际上全是等式即图中从u到v的所有路径长度相同。

于是可以用并查集做

Si表示从i到Fi相差多少。

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <cstring> //一定要记得打！！ 
 4 using namespace std;
 5 #define N 1008
 6 
 7 int T;
 8 int n,m,F[N],S[N];
 9 bool Right;
10 
11 void clean()
12 {
13     memset(S,0,sizeof(S));
14     for (int i = 0;i <= n + 1;i++) F[i] = i;
15     Right = true;
16 }
17 
18 int find(int x)
19 {
20     if (x == F[x]) return x;
21     int fx = F[x];
22     F[x] = find(F[x]);
23     S[x] += S[fx];
24     return (F[x]);
25 }
26 
27 void debug()
28 {
29     for (int i = 0;i <= n;i++) printf("%d ",S[i]);
30     printf("
");
31     for (int i = 0;i <= n;i++) printf("%d ",F[i]);
32     printf("
"); 
33 }
34 
35 void work()
36 {
37     scanf("%d%d",&n,&m);
38     clean();
39     while (m--)
40     {
41         int s,t,v;
42         scanf("%d%d%d",&s,&t,&v); s--;
43         int fx = find(s),fy = find(t);
44         if (fx != fy)
45         {
46             F[fx] = fy;
47             S[fx] = S[t] - S[s] + v;
48         }
49         else if (S[s] - S[t] != v) Right = false;
50 //        debug(); 
51     }
52     Right?printf("true
"):printf("false
");
53 }
54 
55 int main()
56 {
57     scanf("%d",&T);
58     while (T--) work();
59 //    while(1){}
60     return 0;
61 }

View Code