首页 > 代码库 > 【BZOJ1202】【HNOI2005】狡猾的商人 并查集

【BZOJ1202】【HNOI2005】狡猾的商人 并查集

题解:呃,这个题太耿直了。

还能有负收益,也就是一个区间只需要有某段时间没有确定,或者有重叠,那就“一切皆有可能”。

只有边界完全重合的一些区间神马的才能判错。


于是写个耿直的并查集就好了。(可以a~b收益为c,a>b,反正有负收益233)


代码:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 105
using namespace std;
int f[N],l[N],n,m;
void keep(int x)
{
	if(x==f[x])return ;
	keep(f[x]);
	l[x]+=l[f[x]];
	f[x]=f[f[x]];
}
int main()
{
//	freopen("test.in","r",stdin);
	int i,j,k,g;
	int a,b,c;
	for(scanf("%d",&g);g--;)
	{
		int flag=1;
		scanf("%d%d",&n,&m);
		for(i=0;i<=n;i++)f[i]=i,l[i]=0;
		for(i=1;i<=m;i++)
		{
			scanf("%d%d%d",&a,&b,&c),a--;
			keep(a),keep(b);
			if(f[a]==f[b]&&l[a]!=l[b]+c)
			{
				flag=0;
				break;
			}
			l[f[a]]=l[b]+c-l[a];
			f[f[a]]=f[b];
		}
		if(flag)puts("true");
		else puts("false");
	}
}



【BZOJ1202】【HNOI2005】狡猾的商人 并查集