将其转化为图论题。
定义:\(u,v\)为\(a_i\)所代表的点 \(u',v'\)为\(b_i\)所代表的点
对于操作\(2\),将其视为一种权值搬运的操作,从\(u\)到\(v\)或者反过来转移点权。那么我们对\(u,v\)和\(u',v'\)连一条无向边,显然对于一个连通块内的所有点都可以直接或间接的相互转移权值。
在\(u,v\)与\(u',v'\)两者之间做权值转移时等价的,所以要连两条无向边。
对于操作\(1\),我们可以将其转化为一种特殊的操作\(2\),可以发现我们只关心当前权值和目标权值的相对大小。所以操作\(u+1,v+1\)等价于\(u'-1,v+1\)或者\(u+1,v'-1\),也就是转化为了操作2。
按照这样的方式建图,可以发现每一个连通块内的所有点,要么只有\(a\)里面的点,要么只有\(b\)里面的点。如果两者都有,其数量一定相等。
应该如何检验答案呢?
如果\(i,i'\)位于同一个连通块,意味着连通块中必然有等数量的\(a\)点和\(b\)点。该连通块有解,当且仅当其权值和为偶数。
反之,如果位于两个连通块内,则只需要两个连通块权值和相等即说明有解。
用并查集找连通块即可。复杂度\(O(Tn)\)
#include<cstdio>
#include<algorithm>
using namespace std;
int fa[200005],u,v,t,val[200005],n,m,T;
int getf(int v)
{
if (fa[v]!=v) return fa[v]=getf(fa[v]);
else return v;
}
void merge(int x,int y)
{
x=getf(x),y=getf(y);
if (x==y) return ;
fa[x]=y;
val[y]+=val[x];
}
bool check(int x,int y)
{
x=getf(x),y=getf(y);
return x==y;
}
int main()
{
scanf("%d",&T);
for (int F=1;F<=T;F++)
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
{
scanf("%d",&val[i]);
fa[i]=i;
fa[i+n]=i+n;
}
for (int i=1;i<=n;i++) scanf("%d",&val[i+n]);
for (int i=1;i<=m;i++)
{
scanf("%d%d%d",&t,&u,&v);
if (t==1)
{
merge(u,v+n);
merge(v,u+n);
}
else
{
merge(u,v);
merge(v+n,u+n);
}
}
bool flag=true;
for (int i=1;i<=n;i++)
{
if (check(i,i+n))
{
if (val[getf(i)]%2!=0)
{
flag=false;
break;
}
}
else
{
if (val[getf(i)]!=val[getf(i+n)])
{
flag=false;
break;
}
}
}
printf(flag?"YES\n":"NO\n");
}
return 0;
}