[并查集]People on a Line

标签：information People int 查集 Li Di Line fin Ri

题目描述

There are N people standing on the x-axis. Let the coordinate of Person i be xi. For every i, xi is an integer between 0 and 10⁹ (inclusive). It is possible that more than one person is standing at the same coordinate.
You will given M pieces of information regarding the positions of these people. The i-th piece of information has the form (Li,Ri,Di). This means that Person Ri is to the right of Person Li by Di units of distance, that is, xRi−xLi=Di holds.
It turns out that some of these M pieces of information may be incorrect. Determine if there exists a set of values (x1,x2,…,xN) that is consistent with the given pieces of information.

Constraints
1≤N≤100 000
0≤M≤200 000
1≤Li,Ri≤N (1≤i≤M)
0≤Di≤10 000 (1≤i≤M)
Li≠Ri (1≤i≤M)
If i≠j, then (Li,Ri)≠(Lj,Rj) and (Li,Ri)≠(Rj,Lj).
Di are integers.

输入

Input is given from Standard Input in the following format:
N M
L1 R1 D1
L2 R2 D2
:
LM RM DM

输出

If there exists a set of values (x1,x2,…,xN) that is consistent with all given pieces of information, print Yes; if it does not exist, print No.

样例输入 Copy

3 3
1 2 1
2 3 1
1 3 2

样例输出 Copy

Yes

提示

Some possible sets of values (x1,x2,x3) are (0,1,2) and (101,102,103).

---

题目的大致意思就是告诉你两个人a,b还有一个距离d，然后a在b左边d的距离，告诉你有n个人，m组数据，是否存在矛盾   第一想法是高斯消元，但n=1e5太大了。   后来看的题解。   f[x]=y表示x的左边是y,g[x]是x到最左边的距离  

代码

 #pragma GCC optimize(2)
#include<iostream>
using namespace std;
int n,m;
int f[200005],g[200005];
int fin(int x)
{
	if(f[x]==x)return x;
	int a=fin(f[x]),b=f[x];	
	g[x]+=g[b];
	f[x]=a;
	return f[x];
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)f[i]=i;
	for(int i=1;i<=m;i++)
	{
		int a,b,d;
		cin>>a>>b>>d;
		int x=fin(a),y=fin(b);
		if(f[x]==f[y])
		{
			if(g[b]-g[a]!=d)
			{
				cout<<"No\n";
				return 0;
			}
		}
		else
		{
			f[y]=x;
			g[y]=g[a]+d-g[b];
		}
	}
	cout<<"Yes\n";
	return 0;
}

 

标签：information,People,int,查集,Li,Di,Line,fin,Ri
From： https://www.cnblogs.com/qbning/p/17058797.html