BZOJ1202 [HNOI2005]狡猾的商人并查集

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1202

分析:

题目大概就是讲给你一些区间和。问你这些有没有冲突.

然而题目给的又那么少.所以很快应该想到前缀和,来解决问题.
好像又没有什么交集来解决问题。

所以这里可以用带权值并查集。

其中V[x]表示x这个点到它所在联通块的距离.

对于任意给你的区间(x,y);
当x,y都在同一集合里我们只需要判断V[y]-V[x-1]?=Val;
当不在同一集合:

注意下面的x均已经处理成x-1.
p=Find(x),q=Find(y);
我们可以列出几个关系式:
V[x]=S[x]-S[p]
V[y]=S[y]-S[q]
Val=S[y]-S[x]

V[p]=S[p]-S[q]
V[p]=S[x]-V[x]-(S[y]-V[y])
V[p]=V[y]-V[x]+(S[x]-S[y])
V[p]=V[y]-V[x]-Val;

这样就可以并查集合并了.

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int father[501];
int cha[501];

int find_father(int x)
{
	if(father[x]==x)return x;
	int t=find_father(father[x]);
	cha[x]+=cha[father[x]];
	father[x]=t;
	return father[x];
}

int main()
{
	int t,n,m,x,y,z;
	scanf("%d",&t);
	while(t--)
	{
		bool flag=false;
		scanf("%d%d",&n,&m);
		for(int i=0;i<=n;++i)father[i]=i;
		memset(cha,0,sizeof(cha));
		for(int i=1;i<=m;++i)
		{
			scanf("%d%d%d",&x,&y,&z);
			x--;
			int q=find_father(x),p=find_father(y);
			if(q!=p)
			{
				cha[p]=cha[x]-cha[y]+z;
				father[p]=q;
			}
			else {
				if(cha[y]-cha[x]!=z)flag=true;
			}
		}
		if(flag)printf("false\n");
		else printf("true\n");
	}
	return 0;
}

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int father[501];

int cha[501];

int find_father(int x)

{

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

int t=find_father(father[x]);

cha[x]+=cha[father[x]];

father[x]=t;

return father[x];

}

int main()

{

int t,n,m,x,y,z;

scanf("%d",&t);

while(t--)

{

bool flag=false;

scanf("%d%d",&n,&m);

for(int i=0;i<=n;++i)father[i]=i;

memset(cha,0,sizeof(cha));

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

{

scanf("%d%d%d",&x,&y,&z);

x--;

int q=find_father(x),p=find_father(y);

if(q!=p)

{

cha[p]=cha[x]-cha[y]+z;

father[p]=q;

}

else {

if(cha[y]-cha[x]!=z)flag=true;

}

if(flag)printf("false\n");

else printf("true\n");

}

return 0;

}

Update:

又写了一遍.

#include<bits/stdc++.h>//BY:uncle-lu
using namespace std;
template<class T>void read(T &x)
{
	x=0;int f=0;char ch=getchar();
	while(ch<'0'||ch>'9') { f|=(ch=='-'); ch=getchar(); }
	while(ch<='9'&&ch>='0') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
	x = f ? -x : x;
	return ;
}

int Father[110];
int V[110];
int n,m;

int Find_father(int x)
{
	if(Father[x]==x)return x;
	int t=Find_father(Father[x]);
	V[x]+=V[Father[x]];
	Father[x]=t;
	return t;
}

void init()
{
	memset(V,0,sizeof(V));
	for(int i=0;i<=n;++i)Father[i]=i;
	return ;
}

int main()
{
	//freopen("./in","r",stdin);
	int t,x,y,val;
	read(t);
	while(t--)
	{
		read(n);read(m);
		bool flag=false;
		init();
		for(int i=1;i<=m;++i)
		{
			read(x);read(y);read(val);
			x--;
			int p=Find_father(x),q=Find_father(y);
			if(p!=q)
			{
				Father[p]=q;
				V[p]=V[y]-V[x]-val;
			}
			else if(V[y]-V[x]!=val)flag=true;
		}
		if(!flag)printf("true\n");
		else printf("false\n");
	}
	//fclose(stdin);
	return 0;
}

#include<bits/stdc++.h>//BY:uncle-lu

using namespace std;

template<class T>void read(T &x)

{

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

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

while(ch<='9'&&ch>='0') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }

x = f ? -x : x;

return ;

}

int Father[110];

int V[110];

int n,m;

int Find_father(int x)

{

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

int t=Find_father(Father[x]);

V[x]+=V[Father[x]];

Father[x]=t;

return t;

}

void init()

{

memset(V,0,sizeof(V));

for(int i=0;i<=n;++i)Father[i]=i;

return ;

}

int main()

{

//freopen("./in","r",stdin);

int t,x,y,val;

read(t);

while(t--)

{

read(n);read(m);

bool flag=false;

init();

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

{

read(x);read(y);read(val);

x--;

int p=Find_father(x),q=Find_father(y);

if(p!=q)

{

Father[p]=q;

V[p]=V[y]-V[x]-val;

}

else if(V[y]-V[x]!=val)flag=true;

}

if(!flag)printf("true\n");

else printf("false\n");

}

//fclose(stdin);

return 0;

}

没有回路的路