一、题面
二、分析
用并查集可以方便的判断两个位置是否有关系,这种关系可以通过是否有公共父节点判断,如果有公共父节点则可以直接判断是否正确,如果没有公共父节点,就可以把这个条件与之前的联系起来。同时需要设定sum,表示当前点到父节点的权值,这个权值方便后面的判断,这里有几种情况。
假设输入为$(x,y,w)$,那么对应父节点$fx = find(x), fy = find(y)$:
1.如果$fx==fy$:那么可以直接判断$w == sum[x] – sum[y]$.
2.如果$ x < y < fx < fy$:这里需要更新并查集的信息,$par[fx] = fy, sum[fx] = sum[y] – (sum[x] – w)$.
3.如果$ x < fx < y < fy$:此时,$par[fx] = fy, sum[fx] = sum[y] + (w – sum[x])$.
4.如果$ x < y < fy < fx$:此时,$par[fy] = fx, sum[fy] = sum[x] – sum[y] – w$.
分析上面四种情况,可以得出2和3可以合并,对于4,仔细分析一下, 相当于就是3的情况,只是因为$par[fy] = fx$,只是这样可以保证$sum$的值为正。注意在路径压缩时,对$sum$进行更新就可以了。
细心的朋友可能发现了,还有$x = y$的情况呢。对于这种情况,我们可以直接对输入的左值整体再往左移一下,就是输入的$u$变成$u-1$,这个对结果是没有影响的。但是如果不减,我们就要考虑$x=y$的情况了,前面我们已经初始化了$sum$初值为0,并且$x=y$的左右两边的情况我们是不能保证完全清楚的。所以这样把$x=y$变成了$(x-1,y]$这个区间的形式,就让问题又归到了我们上面讨论的情况,更简单了。
三、AC代码
#include <cstdio>
#include <iostream>
#include <cstring>
#include <fstream>
#include <map> using namespace std; const int MAXN = 2e5+;
int par[MAXN];
int sum[MAXN]; void Init()
{
for(int i = ; i < MAXN; i++)
par[i] = i;
memset(sum, , sizeof(sum));
} int Find(int x)
{
if(par[x] == x)
return x;
int fx = par[x];
par[x] = Find(fx);
sum[x] = sum[fx] + sum[x];
return par[x];
} bool Union(int x, int y, int w)
{
int fx = Find(x);
int fy = Find(y);
// if(fx != fy)
// {
// par[fx] = fy;
// sum[fx] = w + sum[y] - sum[x];
// return true;
// }
// else
// {
// return w == sum[x] - sum[y];
// }
if(fx < fy)
{
par[fx] = fy;
sum[fx] = w + sum[y] - sum[x];
return true;
}
else if(fx > fy)
{
par[fy] = fx;
sum[fy] = sum[x] - w - sum[y];
return true;
}
else
{
return w == sum[x] - sum[y];
} } int main()
{
// freopen("input.txt", "r", stdin);
int N, M;
while(scanf("%d %d", &N, &M)!=EOF)
{
Init();
int a, b, w, ans = ;
for(int i = ; i < M; i++)
{
scanf("%d %d %d", &a, &b, &w);
if(!Union(a-, b, w))
ans++;
}
printf("%d\n", ans);
}
return ;
}