T1 : 序列
题意:
一共有 T 组数据, 每组数据有两个长度为 n 的序列 a,b,m 个操作, 问 a 序列是否可以转换成 b, 是输出 YES, 否的话输出 NO.m 个操作分别为 ti,xi,yi, 若 t 为 1, 则 x 和 y 上的数可同时加减一; 若 t 为 2, 则 x 上的数加一同时 y 上的数减一, 或 y 上的数加一同时 x 上的数减一;
大概理解为: 将 a 上的所有数变成 b 上的对应的数, 当 t=1 时可以将 a[x],a[y]同时加任何数, 当 t=2 时可以将 a[x]加任何数同时 a[y]上的数减上相同的数 (相当于把 a[x] 一部分值转到 a[y]上);
列: a : 1 3 5 4 t=1,x=1,y=2 则若 a[1] (1) 要加上 3,a[2] (3) 也必须加上 3,a 变成 4 6 5 4
t=2,x=1,y=2 则若 a[1] (1) 要加上 3,a[2] (3) 必须减去 3,a 变成 4 0 5 4;
数据范围:
1≤T≤10,1≤n,m≤105,1≤ai,bi≤109
分析:
这题可以用图论来做
先定义一个序列 c ,c[i]=a[i]-b[i], 这样我们只要判断 c 中的每一个值是否可以变为零就行了.
然后读入 m 个操作
先不用管 t 为 1 时的情况, 若 t 为 2 的话, 把 x 和 y 之间连一条无向边, 然后将图中的联通块缩点. 因为联通块中的任何俩个数都可以将他们的一部分值互相转换, 所以可以将他们看做一个点, 该点的权值就是联通块中的每一个 c[i]的和.
下面记 i 点所在的联通块为 bel[i].
接下来再操作将 t 为 1 时的情况, 将 bel[x]与 bel[y]之间连一条无向边, 若 bel[x]=bel[y]则用一个 bool 数组表示 bel[x]有自环, 有自环后 bel[x]的值就可以成 2 的倍数增长.
接下来就对新图进行缩点, 可以发现, 若两个点之间的路径长度为偶数时, 两个点间可进行值的转移.
所以我们再将图进行黑白染色, 同色点之间一定长度为偶数的路径, 那么我们就将颜色相同的点进行缩点.
缩到最后, 我们再将判断一下每个联通块是否可以将其的总权值变为零, 如果有一个联通块不能将其总权值变为零, 则输出 NO, 反之输出 YES.
我们再看看如何判断联通块之间是否可以将其总权值变为零.
因为缩点缩到最后一定每个联通块最多只有两个点(黑点和白点), 所以判断一下这两个点可不可以变为零就行了.
只要两个点的权值相同, 那么就可以两个点同时加减变为零. 如果不相等, 如果两个点其中一个有自环, 且两个点权值差为偶数, 那就可以将两个点的值变相同, 之后再进行操作.
因为我们只需要判断联通块是否可以变成零就行了, 所以不用建新图, dfs 一下就行.
代码如下:
- #include<cstdio>
- #include<iostream>
- #include<algorithm>
- #include<cstring>
- #include<vector>
- using namespace std;
- typedef long long LL;
- const int N=1000010;
- LL sum[N];
- int bel[N],a[N],color[N];
- bool book[N];
- vector<int> h[N],g[N];
- struct Node
- {
- int x,y;
- }w[N];
- void dfs1(int u,int c)// 第一次缩点 (t 为 2 时的边)
- {
- bel[u]=c;
- sum[c]+=a[u];
- for(int i=0;i<g[u].size();i++)
- {
- int j=g[u][i];
- if(!bel[j])
- dfs1(j,c);
- }
- }
- bool dfs2(int u,int col,bool &pd,LL &suma,LL &sumb)// 第二次缩点
- {
- if(~color[u]) return color[u]==col;// 若颜色不一样说明有奇数环
- color[u]=col;// 进行染色
- pd|=book[u];// 判断有没有自环
- if(col==0) suma+=sum[u];// 将相同色的点权值相加
- else sumb+=sum[u];
- bool t=true;
- for(int i=0;i<h[u].size();i++)
- {
- int j=h[u][i];
- t&=dfs2(j,col^1,pd,suma,sumb);
- }
- return t;
- }
- int main()
- {
- int T;
- scanf("%d",&T);
- while(T--)
- {
- int n,m;
- int cnt_all=0,cnt=0;
- scanf("%d%d",&n,&m);
- for(int i=1;i<=n;i++) scanf("%d",&a[i]);
- for(int i=1;i<=n;i++)
- {
- int x;
- scanf("%d",&x);
- a[i]=x-a[i];
- g[i].clear();// 将边初始化
- h[i].clear();
- }
- memset(w,0,sizeof(w));
- while(m--)
- {
- int p,x,y;
- scanf("%d%d%d",&p,&x,&y);
- if(p==1)
- {
- w[cnt_all++]={x,y};// 存储当 t 为 1 时的边
- }
- else
- {
- g[x].push_back(y),g[y].push_back(x);//t 为 2 时将 x 与 y 之间连边
- }
- }
- memset(sum,0,sizeof(sum));// 联通块总权值初始化
- memset(bel,0,sizeof(bel));// 每个点属于的联通块
- for(int i=1;i<=n;i++)
- {
- if(!bel[i]) dfs1(i,++cnt);
- }
- memset(book,0,sizeof(book));
- for(int i=0;i<cnt_all;i++)
- {
- int x=bel[w[i].x],y=bel[w[i].y];
- if(x==y) book[x]=true;// 判断自环
- else
- {
- h[x].push_back(y);// 不是自环则加边
- h[y].push_back(x);
- }
- }
- bool ans=1;
- memset(color,-1,sizeof(color));// 初始化颜色
- for(int i=1;i<=cnt;i++)
- {
- if(color[i]==-1)// 若没被染过色
- {
- bool pd=false;// 判断自环
- LL suma=0,sumb=0;// 黑色和白色点的权值总和
- if(dfs2(i,0,pd,suma,sumb))
- {
- if(pd) ans&=(suma+sumb)%2==0;// 判断联通块权值是否可以变为零
- else ans&=suma==sumb;
- }
- else
- {
- ans&=(suma+sumb)%2==0;
- }
- }
- }
- if(ans) puts("YES");
- else puts("NO");
- }
- }
来源: http://www.bubuko.com/infodetail-3451621.html