Luogu P6185 [NOI Online #1 提高组]序列
小 D 有一个长度为 n 的整数序列 a_{1 \dots n},她想通过若干次操作把它变成序列 b_i。
小 D 有 m 种可选的操作,第 i种操作可使用三元组 (t_i,u_i,v_i)描述:若t_i=1,则她可以使 a_{u_i} 与a_{v_i}都加一或都减一;若t_i=2,则她可以使 a_{u_i} 减一、a_{v_i} 加一,或是 a_{u_i} 加一、a_{v_i} 减一,因此当 u_i=v_i 时,这种操作相当于没有操作。
小 D 可以以任意顺序执行操作,且每种操作都可进行无限次。现在给定序列与所有操作,请你帮她判断是否存在一种方案能将 a_i 变为b_i。题目保证两个序列长度都为 n。若方案存在请输出
YES
,否则输出NO
。
我们可以把每个数字当作一个点,t=2了话将u和v连起来。
如图所示,发现在一个连通块的点可以任意加减,但是连通块总和不变。
(虽然1和3没有直接连接,但是2使他们处于同一联通块,所以间接等于直接连了起来。)
我们所以把一个连通块缩成一个点就好。
然后看操作1
缩点后的操作1相当于可以将2个连通块同时加减,然后传递一下就会发现,可以实现操作2
如果缩点后的图是二分图
那么可以左部和右部内部之间 可以借助两部之间的操作1,来完成内部之间的操作2。
那么现在相当于只剩下左部和右部两个点了,只用保证左部之和等于右部,就可以通过操作1达到题目要求
如果不是二分图
考虑原二分图内部之间有连接,可以执行操作1,借助二分图左右两边的操作1,可以实现内部任一点的操作1。
也就是内部两点可以同时加1或者减1,等效于左部或右部加2或减2,执行无数次就是内部可以加减任意偶数,而且此时仍具有前面二分图的性质
于是只用保证左右两边奇偶性相同,便可以达到题目要求。
#include<bits/stdc++.h>
#define ll long long
const int N = 1e5+10;
std::vector<int> G[N];
int fa[N];
ll a[N],b[N],c[N], v[N];
int n,m;
ll s[10];
int p[N],q[N],tot;
int get(int x){
if(!fa[x]) return x;
return fa[x]=get(fa[x]);
}
int dfs(int x,int k){
int S=G[x].size();
v[x]=k;
s[k]+=c[x];
int fl=1;
for(int i=0;i<S;++i){
int vv=G[x][i];
if(v[vv]==v[x]){
fl=0;
}
else
if(!v[vv])
fl&=dfs(vv,3-k);
}
return fl;
}
int main(){
// freopen("da.in","r",stdin);
int T;
scanf("%d",&T);
while(T--){
memset(fa,0,sizeof(fa));
memset(v,0,sizeof(v));
memset(c,0,sizeof(c));
tot=0;
for(int i=1;i<=n;++i){
G[i].clear();
}
scanf("%d %d",&n,&m);
for(int i=1;i<=n;++i){
scanf("%lld",&a[i]);
}
for(int i=1;i<=n;++i){
scanf("%lld",&b[i]);
}
for(int i=1;i<=m;++i){
int t,u,v;
scanf("%d %d %d",&t,&u,&v);
if(t==1){
tot++;
p[tot]=u;
q[tot]=v;
}
else{
u=get(u),v=get(v);
if(u!=v)
fa[u]=v;
}
}
for(int i=1;i<=n;++i)
c[get(i)]+=a[i]-b[i];
for(int i=1;i<=tot;++i){
int u=get(p[i]);
int v=get(q[i]);
G[u].push_back(v);
G[v].push_back(u);
}
int ok=1;
for(int i=1;i<=n;++i){
if(i==get(i)&&!v[i]){
s[1]=s[2]=0;
int fl=dfs(i,1);
if(fl){
if(s[1]!=s[2])
ok=0;
}
else{
if((s[1]+s[2])&1)
ok=0;
}
}
}
if(ok) puts("YES");
else puts("NO");
}
return 0;
}
0 条评论