BZOJ1202：[HNOI2005]狡猾的商人

浅谈并查集：https://www.cnblogs.com/AKMer/p/10360090.html

题目传送门：https://lydsy.com/JudgeOnline/problem.php?id=1202

带权并查集，同POI1733。

时间复杂度：\(O(Tm\alpha{n})\)

空间复杂度：\(O(n)\)

代码如下：

#include <cstdio>

using namespace std;

const int maxn=105;

int n,m;

int fa[maxn],d[maxn];

int read() {

	int x=0,f=1;char ch=getchar();

	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

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

	return x*f;

}

int find(int x) {

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

	int tmp=fa[x];

	fa[x]=find(fa[x]);

	d[x]+=d[tmp];

	return fa[x];

}

int main() {

	int T=read();

	while(T--) {

		n=read(),m=read();

		for(int i=0;i<=n;i++)

			fa[i]=i,d[i]=0;

		bool ans=1;

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

			int l=read()-1,r=read(),x=read();

			int p=find(l),q=find(r);

			if(p==q&&d[r]-d[l]!=x) {ans=0;break;}

			if(p!=q)fa[p]=q,d[p]=d[r]-d[l]-x;

		}

		if(ans)puts("true");

		else puts("false");

	}

	return 0;

}

巴特西

BZOJ1202：[HNOI2005]狡猾的商人

最新文章

热门文章