「Bzoj 1202」「HNOI2005」狡猾的商人 (并查集+前缀和/差分约束+前缀和)

发表于 | 分类于 | | + s

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检查是否有解

并查集维护前缀和：

#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;
}
------ 本文结束 ------