题目

传送门

思路

可以考虑先用二操作进行连边

现在我们就面对了一个个的块

因为二操作不会改变整个块的和

所以我们就可以将一个块缩成一个点

之后我们在考虑1操作

一样的，我们用1操作针对缩了之后的点进行连边

很明显，如果有环（包括自环），这一个块的和可以任意的+2或者-2

考虑无解的情况

一个块的和为奇数，肯定无解

或者是一个块的和为偶数，但是其中并没有环

代码

#include<iostream>
#include<vector>
#include<cstdio>
using namespace std;
struct node
{
    int t;
    int u;
    int v;
}opt[100005];
int t;
int n,m;
int a[100005];
int b[100005];
long long c[100005];
int fa[2][100005];
bool vis[100005];
bool f[100005];
vector<int> g[100005];
void makeset()
{
    for(int i=1;i<=n;i++)
    {
        c[i]=0;
        g[i].clear();
        vis[i]=0;
        f[i]=0;
        fa[0][i]=fa[1][i]=i;
    }
}
int findset(int _ind,int u)
{
    if(fa[_ind][u]!=u)
        fa[_ind][u]=findset(_ind,fa[_ind][u]);
    return fa[_ind][u];
}
void unionset(int _ind,int a,int b)
{
    int u=findset(_ind,a);
    int v=findset(_ind,b);
    fa[_ind][v]=u;
}
void dfs(int u)
{
    f[u]=1;
    for(int i=0;i<g[u].size();i++)
    {
        int v=g[u][i];
        if(f[v]==0)
        {
            dfs(v);
            if(vis[v])
                vis[u]=1;
            c[u]-=c[v];
        }
    }
}
void c_in()
{
    scanf("%d %d",&n,&m);
    makeset();
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&b[i]);
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d %d",&opt[i].t,&opt[i].u,&opt[i].v);
        if(opt[i].u>opt[i].v)
            swap(opt[i].u,opt[i].v);
    }
    for(int i=1;i<=m;i++)
        if(opt[i].t==2)
            if(findset(0,opt[i].u)!=findset(0,opt[i].v))
                unionset(0,opt[i].u,opt[i].v);
    for(int i=1;i<=m;i++)
    {
        if(opt[i].t==1)
        {
            int fau=findset(0,opt[i].u);
            int fav=findset(0,opt[i].v);
            if(findset(1,fau)!=findset(1,fav))
            {
                unionset(1,fau,fav);
                g[fau].push_back(fav);
                g[fav].push_back(fau);
            }
            else
            {
                vis[fau]=1;
            }
        }
    }
    for(int i=1;i<=n;i++)
        c[findset(0,i)]+=(a[i]-b[i]);
    for(int i=1;i<=n;i++)
    {
        if(f[findset(0,i)]==0)
        {
            int u=findset(0,i);
            dfs(u);
            if(c[u]<0)
                c[u]=-c[u]; 
            if(c[u]!=0)
            {
                if(c[u]%2==1||(c[u]%2==0&&vis[u]==0))
                {
                    printf("NO\n");
                    return;
                }
            }
        }
    }
    printf("YES\n");
}
int main()
{
    //freopen("sequence.in","r",stdin);
    //freopen("sequence.out","w",stdout);
    scanf("%d",&t);
    for(int i=1;i<=t;i++)
        c_in();
    return 0;
}

习题：序列（并查集）

原文：https://www.cnblogs.com/loney-s/p/12439030.html