Bzoj 1202(并查集+前缀和/差分约束+前缀和)

BZOJ 1202
方法一:
用并查集维护前缀和的差值。设前缀和$s_i$,$c_i$为$s_i-s_{rt}$的值($rt$是这个并查集的根)。

每次查询,如果$x-1,y$属于一个集合,那么直接查询$c_y-c_{x-1}$。
证明:$s_y=c_y+s_{rt}, s_{x-1}=c_{x-1}+s_{rt}$,那么$s_y-s_{x-1}=c_y+s_{rt}-(c_{x-1}+s_{rt})=c_y-c_{x-1}$。

如果不在一个集合,那么直接合并,$father(rtx)=rty$,($rtx$是$x-1$的根, $rty$是$y$的根),这个时候$c_{rtx}$改变了,$c_{rtx}=c_y-c_{x-1}-v$。
证明:$s_{rty}=s_y-c_y, s_{rtx}=s_{x-1}-c_{x-1}$
$c_{rtx}=s_{rtx}-s_{rty}$
$=s_{x-1}-c_{x-1} - (s_y-c_y)$
$=-(c_{x-1}-c_y)-(s_{y}-s_{x-1})$
$=c_y-c_{x-1}-v$

方法二:
用差分约束维护前缀和,设前缀和$s_i$。
由题意得$s_y-s_{x-1}=v$
将不等式规范化,得$s_y-s_{x-1}\leq v, s_y-s_{x-1}\geq v$
即$s_y-s_{x-1}\leq v, s_{x-1}-s_{y}\leq -v$
然后用SPFA检查是否有解

并查集维护前缀和:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 100 + 5;
int n, m, flag, f[MAXN], c[MAXN];
void clean() {
flag = 0;
for (int i=0;i<=n;i++) f[i] = i, c[i] = 0;
}
int find(int x) {
if (x == f[x]) return x;
int t = find(f[x]);
c[x] += c[f[x]];
return f[x] = t;
}
void ins(int a, int b, int v) {
int x = find(a), y = find(b);
if (x != y) {
f[x] = y;
c[x] = c[b] - c[a] - v;
} else if (c[b] - c[a] != v) flag = 1;
}
void solve() {
scanf("%d%d", &n, &m);
clean();
while (m--) {
int s, t, v;
scanf("%d%d%d", &s, &t, &v);
ins(s - 1, t, v);
}
if (!flag) printf("true\n"); else printf("false\n");
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
int T; scanf("%d", &T);
while (T--) solve();
return 0;
}
------ 本文结束 ------