首页 > 其他分享 >CF228E 题解

CF228E 题解

时间:2024-08-05 21:38:44浏览次数:14  
标签:二分 color 题解 int 简述 CF228E

CF228E 题解

题目简述

给定一个 \(n\) 个点,\(m\) 条边的无向图,每条边都为 \(0\) 或 \(1\),可以进行若干次操作,与此点相连的所有点权值取反,求一种方案使得所有边都变为 \(1\)。

前置知识

  • 二分图
  • 二分图染色

思路简述

首先明白一点:对于同一条边,操作偶数次是没有必要的!因为最终会回到初始状态。

对于任意一条边 \(i\),有:

若 \(v_i = 0\),则状态为 \((x_i,y_i)=(0,1)\) 或 \((x_i,y_i)=(1,0)\)。

若 \(v_i=1\),则状态为 \((x_i,y_i)= (0,0)\) 或 \((x_i,y_i)=(1,1)\)。

然后我们就可以想到思路了。

用一个 color 数组来存储某个点 \(x\) 是没被染色(color[x]=-1),还是染为黑或白色(color[x] 等于 \(0\) 或 \(1\))。

如果遇到某一条边,两个顶点颜色一样,则输出 Impossible,无解。

否则统计某种颜色的顶点个数,再依次输出即可。

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=105,M=N*(N-1)/2;
int n,m,color[N],u,v,op,cnt_ans;
struct E{
	int from,to,pre,co;
}e[M<<1];
int head[N],cnt_e;
void add(int from,int to,int co)
{
	e[++cnt_e].from=from;
	e[cnt_e].to=to;
	e[cnt_e].pre=head[from];
	e[cnt_e].co=co;
	head[from]=cnt_e;
	return;
}
void dfs(int u,int co)
{
	color[u]=co;
	for(int i=head[u];i;i=e[i].pre)
	{
		int v=e[i].to,col=e[i].co;
		if(!col)
		{
			if(color[v]==-1)
				dfs(v,co^1);
			else
			{
				if(color[v]==color[u])
				{
					printf("Impossible\n");
					exit(0);
				}
			}
		}
		else
		{
			if(color[v]==-1)
				dfs(v,co);
			else
				if(color[u]!=color[v])
					printf("Impossible\n"),exit(0); 
		}
	}
	return;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		color[i]=-1;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&u,&v,&op);
		add(u,v,op);
		add(v,u,op);
	}
	for(int i=1;i<=n;i++)
		if(color[i]==-1)
			dfs(i,0);
	for(int i=1;i<=n;i++)
		if(!color[i])
			++cnt_ans;
	printf("%d\n",cnt_ans);
	for(int i=1;i<=n;i++)
		if(!color[i])
			printf("%d ",i);
	puts("");
	return 0;
}

标签:二分,color,题解,int,简述,CF228E
From: https://www.cnblogs.com/Atserckcn/p/18344113

相关文章

  • [Violet 6]故乡的梦 题解
    前言题目链接:Hydro&bzoj。题意简述无向联通图给出起点终点,多次询问删边后最短路,或报告不连通。\(n,m,q\leq2\times10^5\)。题目分析首先想到,如果删掉的边不是原来最短路的边,那么最短路不会发生变化。因此我们只需考虑删除了原来在最短路上的边。不妨把原先最短路任......
  • 洛谷-P9830 题解
    思路分析分析样例:见红线,长宽各为2,存在格点;黄线长2宽3,没有格点。考虑延长黄线使得长4宽6,发现有格点。思考格点,如果长和宽都可以被分成\(p\timesl\)的格式,则存在格点。那么,就能想出:推论1:对于\((0\,\0)\)和\((x\,\y)\)之间没有格点,当且仅当\(\gcd(x\,......
  • P9596 冒泡排序 2 题解
    题目链接。Statement记\(f(A)\)为序列\(A\)的冒泡排序趟数,操作:单点改,全局查\(f(A)\).\(n,m\le5\cdot10^5\),值域1e9.Solution结论:\[Ans=\max_{i\in[1..n]}\left\{\sum_{j\in[1..i]}[A_j>A_i]\right\}\]怎么观察出来啊QAQ证明:对于每个位置\(p\),观察到每趟都......
  • AGC046C 题解
    blog。好菜啊,不会这题,来写个题解/kel。很难直接做,先找一点性质:操作只改变相对顺序,而总数不变。这启示我们记录每个\(0\)前面的极长\(1\)连续段长度。记第\(i(1\lei\leC)\)个\(0\)对应长度为\(a_i\),就存在下面的等价表述:每次操作可以选定\(i,j(1\lei<j\leC)\),......
  • 洛谷-P9574 题解
    思路分析分析样例:==TTBTBTTBTBTTTBTTB->TTBTTBBTTBTTTBTTB->TTBTTBTBBTTTTBTTB->TTBTTBTBBTTTTTBBT----1-----2-----3---4--观察区块2,发现BTTB进行操作后与右边的TB再次构成BTTB,我们发现在这个区块内,可以从左向右不断操作,我们称这种特性为传递性,可......
  • AT_abl_e Replace Digits 题解
    题目传送门前置知识线段树解法需要维护区间信息,考虑使用线段树维护。预处理出\(\overline{xx\dotsx}\),其中\(x\in\{1,2,3,4,5,6,7,8,9\}\),便于区间赋值。然后就是普通的线段树板子了。代码#include<bits/stdc++.h>usingnamespacestd;#definelllonglong#de......
  • AGC027C 题解
    注意到如果可以构造出所有由\(\texttt{A}\)和\(\texttt{B}\)组成的字符串,那么在图上游走的路径必须成环,并且的环上的每一个点都必须同时有一个\(\texttt{A}\)邻居和\(\texttt{B}\)邻居。于是可以考虑把点拆分为入点和出点,相邻两个点为\(\texttt{AA},\texttt{BB}\)的,从......
  • npm下载包时报错 Unexpected token ‘.‘问题解决
    项目场景:项目需要使用node18.12.0以上版本的,但是npm下载显示异常问题描述当通过nvm切换nodejs版本为16以上时,npminstall[package]报错:Unexpectedtoken'.'原因分析:提示:该问题不是npm的问题,也不是nodejs的问题,是nvm-windows的问题我是通过nvm-windows已经更新版本......
  • 《数据结构习题解析与实验指导_李冬梅,张琪编著》总结出的大纲
        下面大纲为《数据结构习题解析与实验指导_李冬梅,张琪编著》总结出的大纲,可装13学习下:          ......
  • Codeforces Round 963 (Div. 2) D题解
    CodeforcesRound963D题目描述给定两个正整数n和k以及另一个由n个整数组成的数组a。在一次操作中,可以选择a中大小为k的任意一个子数组,然后将其从数组中删除,而不改变其他元素的顺序。更正式地说,假设(l,r)是对子数组a[l],a[l+1],...,a[r]的操作,使得r-l+1......