Bzoj1202/洛谷P2294 [HNOI2005]狡猾的商人（带权并查集/差分约束系统）

题面

Bzoj

洛谷

题解

考虑带权并查集，设$f[i]$表示$i$的父亲（$\forall f[i]<i$），$sum[i]$表示$\sum\limits_{j=fa[i]}^ia[j]$，对于一组输入的$[x,y,z]$，有：

1.如果$f[x-1]=f[y]$

这个时候直接判断$sum[y]-sum[x-1]$是否等于$z$就行了。

2.如果$f[x-1]\not= f[y]$

将$f[y]$的$f$定为$f[x-1]$，则$sum[f[y]]=sum[x-1]+z-sum[y]$

如果要用差分约束系统来写，就是打板子判负/正环了，但是带权并查集更好写

#include <cmath>

#include <cstdio>

#include <cstring>

#include <algorithm>

using std::min; using std::max;

using std::swap; using std::sort;

typedef long long ll;

template<typename T>

void read(T &x) {

    int flag = 1; x = 0; char ch = getchar();

    while(ch < '0' || ch > '9') { if(ch == '-') flag = -flag; ch = getchar(); }

    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); x *= flag;

}

const int N = 1e2 + 10;

int t, n, m, fa[N]; ll s[N];

int find (int x) {

    if(fa[x] == -1) return x;

    int tmp = find(fa[x]);

    s[x] += s[fa[x]];

    return fa[x] = tmp;

}

int main () {

	read(t);

	while(t--) {

		bool fail = false;

		read(n), read(m);

		memset(fa, -1, sizeof fa);

		memset(s, 0, sizeof s);

		int x, y; ll z;

		for(int i = 1; i <= m; ++i) {

			read(x), read(y), read(z), --x;

			int fx = find(x), fy = find(y);

			if(fx == fy) {

				if(s[y] - s[x] != z) {

					fail = true; break;

				}

			} else fa[fy] = fx, s[fy] = s[x] + z - s[y];

		}

		puts(fail ? "false" : "true");

	}

	return 0;

}

巴特西

Bzoj1202/洛谷P2294 [HNOI2005]狡猾的商人（带权并查集/差分约束系统）

题面

题解

最新文章

热门文章