[NOI Online 提高组]序列 (并查集+二分图判定)

[NOI Online 提高组]序列 (并查集+二分图判定)

题面

略

分析

首先不妨令(b_i=b_i-a_i),这样我们需要通过一系列操作把所有(b_i)变成0.

我们把每个位置看成点。
对于所有2操作连边。如果两个位置连通,就可以使一个位置+1,一个位置-1.那么对于一个连通块,无论我们怎么操作总和都不变。因此我们用并查集将连通块缩成一个点,缩成点的权值为块内所有点的权值之和。

再对于1操作连边。
如果该图是二分图,那么选一条边+1,左部和右部节点的和都会+1.因此无论我们怎么操作左右部节点的差都不变. 那么如果左右部节点的权值之和不相等,那么一定无解。否则容易构造出一种方案。
如果该图不是二分图,无论我们怎么操作总和的奇偶性不变,因为要么+2,要么-2.那么如果总和为奇数,那么一定无法变成0,无解。

那么并查集缩点,再dfs跑二分图判定，同时统计一下节点权值和即可。

代码

#include<iostream>
#include<cstdio>
#include<vector> 
#include<cstring>
#define maxn 100000
using namespace std;
int T,n,m;
int a[maxn+5],b[maxn+5];
struct oper {
	int t;
	int u;
	int v;
} q[maxn+5];

struct disjoint_set {
	int fa[maxn+5];
	int find(int x) {
		if(fa[x]==x) return x;
		else return fa[x]=find(fa[x]);
	}
	void merge(int x,int y) {
		fa[find(x)]=find(y);
	}
	void ini(int n){
		for(int i=1;i<=n;i++) fa[i]=i;
	}
}S;
int sum[maxn+5];//每个连通块的权值之和 

vector<int>E[maxn+5];//缩点之后的图 
void add_edge(int u,int v){
	E[u].push_back(v);
	E[v].push_back(u);
}
int col[maxn+5];//二分图染色 
int tot[3];//二分图两边节点的权值和 
bool dfs(int x,int c){
	col[x]=c;
	tot[c]+=sum[x];
	bool flag=1;
	for(int i=0;i<(int)E[x].size();i++){
		int y=E[x][i];
		if(!col[y]){
			if(!dfs(y,3-c)) flag=0;	//这里不能直接break,因为要遍历所有节点求和 
		}else if(col[y]==c) flag=0;
	}
	return flag;
}

void clear(){
	for(int i=1;i<=n;i++){
		sum[i]=col[i]=0;
		E[i].clear();
	}
	S.ini(n);
}
int main() {
	scanf("%d",&T);
	while(T--){
		scanf("%d %d",&n,&m);
		clear();
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		for(int i=1;i<=n;i++){
			scanf("%d",&b[i]);
			b[i]=b[i]-a[i];
		}
		for(int i=1;i<=m;i++) scanf("%d %d %d",&q[i].t,&q[i].u,&q[i].v);
		for(int i=1;i<=m;i++){//按操作2连边 
			if(q[i].t==2) S.merge(q[i].u,q[i].v);
		}
		for(int i=1;i<=n;i++) sum[S.find(i)]+=b[i];
		for(int i=1;i<=m;i++){//缩点后按操作1连边 
			if(q[i].t==1) add_edge(S.find(q[i].u),S.find(q[i].v));
		}
		bool flag=1;
		for(int i=1;i<=n;i++){
			if(S.find(i)==i){//遍历缩点后的每个节点 
				if(col[i]) continue;
				tot[1]=tot[2]=0;
				bool is_bi=dfs(i,1);
				if(is_bi&&tot[1]!=tot[2]) flag=0;
				if(!is_bi&&(tot[1]-tot[2])&1) flag=0;
			}
		}
		if(flag) puts("YES");
		else puts("NO");
	} 
}