平面设计网课平台哪个好,seo初级入门教程,青岛房产网链家,西安做服务器的公司传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a;
给你两个完全相同的图#xff0c;现在两个图的每个点上有一个值valvalval并且有一个颜色colcolcol#xff0c;颜色只能为红色或黑色#xff0c;注意两个图只是长得一样#xff0c;点的权值和颜色并不一定…传送门
文章目录题意思路题意
给你两个完全相同的图现在两个图的每个点上有一个值valvalval并且有一个颜色colcolcol颜色只能为红色或黑色注意两个图只是长得一样点的权值和颜色并不一定相同。现在你可以进行若干次操作每次操作可以选择一条边两边的两个点交换其valvalval如果这两个点的颜色相同那么颜色取反即红色变黑色黑色变红色否则颜色不变。 问你能否经过若干次操作使得两张图每个点对应的值和颜色相同。 n≤1e6n\le1e6n≤1e6
思路
比较显然的是我们只用操作一个图即可并且每个每个联通块是独立的。 我们考虑单个连通块怎么判断首先肯定是其valvalval的可重集合是相等的才可以其次我们就需要转换一下他的操作可以发现我们的操作等价于将u,vu,vu,v的val,colval,colval,col交换之后再将u,vu,vu,v的colcolcol都取反。不看valvalval的话这就是一个经典的二分图模型可以发现一个数字被交换了奇数次那么他的颜色就会取反否则不变所以我们考虑将其分为二分图和非二分图来考虑。 (1)(1)(1)如果这个图是一个二分图那么我们用染色法将其分成两部分设染的色为nownownow考虑要将u,vu,vu,v两个位置对换如果u,vu,vu,v在二分图的同一边的话他们只能颜色相同才可以因为他们之间的路径长度为偶数不会改变颜色。如果他们不在一边那么他们颜色必须不同原因同上。更具体点来说我们将其按照now⊕colnow\oplus colnow⊕col分成两个可重集合判断两个图的对应集合是否相同即可。 (2)(2)(2)如果这个图不是一个二分图那么他一定存在一个奇环我们可以在有奇环的情况下每次翻转两个位置的颜色由于一次翻转两个颜色所以不改变奇偶性只需要判断一下初始的时候他们的某个颜色是否不同。
实现起来还是有点技巧的。
// Problem: G - Power Station of Art
// Contest: Virtual Judge - 2021多校第六场补题
// URL: https://vjudge.net/contest/451552#problem/G
// Memory Limit: 524 MB
// Time Limit: 5000 ms
//
// Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#includerandom
#includecassert
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].ltr[u].r)1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
// void rd_ac() { freopen(d://dp//1007.in,r,stdin); freopen(d://dp//ac.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n,m;
int st[N];
int val[3][N],p[3][N],iv[2];
vectorintv[N];
char s[N];
bool flag;
vectorintid[3],col[3][3];void dfs(int u,int c) {if(st[u]!-1) {if(st[u]!c) flagfalse;return;}st[u]c;for(int i1;i2;i) {id[i].pb(val[i][u]);col[i][c^p[i][u]].pb(val[i][u]);iv[i]p[i][u];}for(auto x:v[u]) dfs(x,c^1);
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);// rd_ac();int _; scanf(%d,_);while(_--) {scanf(%d%d,n,m);for(int i1;in;i) v[i].clear(),st[i]-1;for(int i1;im;i) {int a,b; scanf(%d%d,a,b);v[a].pb(b); v[b].pb(a);}for(int i1;i2;i) {for(int j1;jn;j) scanf(%d,val[i][j]);scanf(%s,s1);for(int j1;jn;j) p[i][j]s[j]R? 1:0;}int ans1;for(int i1;in;i) {if(st[i]-1) {flagtrue; for(int j1;j2;j) {id[j].clear();col[j][0].clear();col[j][1].clear();}iv[1]iv[2]0;dfs(i,0);for(int j1;j2;j) {sort(id[j].begin(),id[j].end());sort(col[j][0].begin(),col[j][0].end());sort(col[j][1].begin(),col[j][1].end());}if(id[1]!id[2]) ans0;if(flag(col[1][0]!col[2][0]||col[1][1]!col[2][1])) ans0;if(!flagabs(iv[1]-iv[2])%2!0) ans0;}}if(ans) puts(YES);else puts(NO);for(int i1;in;i) v[i].clear();}return 0;
}
/**/
