P6185 [NOI Online #1 提高组] 序列

给定两个长度为n的序列\(A\)，\(B\)。

有m个可用的操作\((t_i,u_i,v_i)\)。

\(t\)代表操作类型。

当\(t=1\)时，表示能够将\(A_{u_i}\)和\(A_{v_i}\)同时\(+1\)；

当\(t=2\)时，表示能够将\(A_{u_i}\)和\(A_{v_i}\)其中一者\(+1\)，另者\(-1\)；

所有操作使用顺序和次数不限，问能否使得\(A\)变成\(B\)

link

sol

先将类型\(2\)的边连接。我们会得到一些连通块。

由于连通分量中任意两点都存在路径，所以对于任意\((u,v)\)我们可以通过\((u,v)\)这条路径使得\(A_u+1\)，\(A_v-1\)。

由此易得对于一个连通分量，我们可以在不改变整个连通分量点权和的前提下任意改变其中节点的值。

这部分就可以拿并查集缩点掉了（

缩点后将类型\(1\)的边连接。

(1)此时的图如果是二分图，那么显然，我们可以在二分图两侧增量相同的前提下任意改变节点的值。

(2)如果不是二分图，也就是存在奇环，显然我们可以通过【一个节点+这个节点到奇环的路径+这个奇环】这样一个组合来使得这个节点 \(\pm\) 一个偶数。

由此易得，我们可以在点权和增量为偶数的前提下任意改变其中节点的值。

然后写法就很显然了（）

先连类型\(2\)的边，用并查集染色缩点并计算缩点后点权；再连\(1\)边。对于新图的每个连通分量，用黑白染色判定是否为二分图，染色过程分别统计黑白增量\(wb_i-wa_i\)的和。如果是二分图就判断黑白增量是否相等，如果不是就判断（伪）黑白增量（即总增量）的总和是否为偶数

我不知道负数mod会发生什么（）所以判断增量奇偶的时候+了个巨大偶数

第一次编译运行没过样例 + 第一次提交 WA 55pts 错在同个地方，就是并查集染色后建边的地方，前者是因为没按颜色建边而按点编号建边，后者是因为没建双向边

没因为多测初始化的问题挂掉，还好...

但虽然整体蛮顺利，完成代码本身还是花了将近1h的样子。太慢了（sad（虽然我一边写还在反复尝试严谨证，不过最后一写总结就清楚了

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cmath>

#define MAXN (int)(1e5+233)

#define MAXM (int)(1e5+233)

#define MAXAB (int)(1e9+233)

using namespace std;

int n,m;

int a[MAXN],b[MAXN];

long long wa[MAXN],wb[MAXN];

long long sum1,sum2;

struct qwq

{

	int nex,to;

}e[MAXM<<1];

int h[MAXN],tot=0;

struct edgee

{

	int u,v;

}E[MAXM];

int Ecnt=0;

inline void add(int x,int y)

{

	e[++tot].to=y;

	e[tot].nex=h[x];

	h[x]=tot;

}

int fa[MAXN];

int found(int x)

{

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

	return fa[x]=found(fa[x]);

}

int col[MAXN],c_count=0;

int typ[MAXN];

inline void INIT() { for (int i=1;i<=n;i++) fa[i]=i,h[i]=0,typ[i]=0,wa[i]=0,wb[i]=0,col[i]=0; tot=0; c_count=0; Ecnt=0; }

bool dfs_bina(int x)

{

	if (typ[x]==1) sum1+=(wb[x]-wa[x]);

	else if (typ[x]==2) sum2+=(wb[x]-wa[x]);

	bool wnw=true;

	for (int i=h[x],y;i;i=e[i].nex)

	{

		y=e[i].to;

		//printf("Edge: %d %d\n",x,y);

		if (!typ[y])

		{

			typ[y]=3-typ[x];//rem INIT typ[x]

			if (!dfs_bina(y)) wnw=false;

		}

		else if (typ[y]==typ[x]) wnw=false;

	}

	return wnw;

}

inline bool sol2(int x)

{

	sum1=sum2=0;

	typ[x]=1;

	bool wnw=dfs_bina(x);

//	printf(":::%d %lld %lld\n",wnw,sum1,sum2);

	if (wnw)

	{

		if (sum1==sum2) return true;

		else return false;

	}

	else

	{

		if ((sum1+sum2+1000000000)&1) return false;

		else return true;

	}

}

inline void sol()

{

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

	INIT();

	for (int i=1;i<=n;i++) scanf("%d",&a[i]);

	for (int j=1;j<=n;j++) scanf("%d",&b[j]);

	for (int i=1,t,u,v,fu,fv;i<=m;i++)

	{

		scanf("%d%d%d",&t,&u,&v);

		if (t==1) E[++Ecnt]=(edgee){u,v};

		else

		{

			fu=found(u); fv=found(v);

			if (fu!=fv) fa[fu]=fv;

		}

	}

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

		if (fa[i]==i) col[i]=++c_count;

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

		col[i]=col[found(i)],wa[col[i]]+=a[i],wb[col[i]]+=b[i];

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

//		if (col[E[i].u]!=col[E[i].v])

			add(col[E[i].u],col[E[i].v]),add(col[E[i].v],col[E[i].u]);

	bool answer=1;

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

		if (!typ[i]) answer&=sol2(i);

	if (answer) printf("YES\n");

	else printf("NO\n");

	return;

}

int main()

{

	int T;

	scanf("%d",&T);

	while (T--) sol();

	return 0;

}

P6185 [NOI Online #1 提高组] 序列的相关教程结束。