题解
先看成前缀和,这样就是维护 \(pre[r],pre[l-1]\) 两点之间的权值
如果是false,代表存在矛盾,且矛盾出现在回路
我们可以把这个回路之前的元素看成一个集合,如果新加入的边使得原先两点间的权值不等便失效
而对于一个集合里的元素,由于相加具有矢量特性,所以我们维护集合内每个点到集合首领的权值,然后集合内之间的权值就很好求了
code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int fa[105];
int val[105]={0};
int finds(int now)
{
if(now==fa[now]) return now;
int fx=finds(fa[now]);
val[now]+=val[fa[now]];
fa[now]=fx;
return fa[now];
}
void init(int n)
{
for(int i=0;i<=n;i++)
{
fa[i]=i;
val[i]=0;
}
}
void solve()
{
int n,m;
cin>>n>>m;
init(n);
int flag=1;
for(int i=1;i<=m;i++)
{
int x,y,v;
cin>>x>>y>>v;
x--;
int fx=finds(x),fy=finds(y);
if(fx==fy)
{
if(val[x]-val[y]!=v) flag=0;
continue;
}
fa[fx]=fy;
val[fx]=v+val[y]-val[x];
}
if(flag) puts("true");
else puts("false");
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t=1;
cin>>t;
while(t--) solve();
return 0;
}
标签:fx,val,int,fa,HNOI2005,权值,now,P2294,狡猾
From: https://www.cnblogs.com/pure4knowledge/p/18319587