Codeforces 741C Arpa’s overnight party and Mehrdad’s silent entering【二分图染色】

68 阅读 0 评论 45 点赞

我是靠谱客的博主高挑台灯，最近开发中收集的这篇文章主要介绍Codeforces 741C Arpa’s overnight party and Mehrdad’s silent entering【二分图染色】，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

这道题呢是何思齐学长给我们讲构造的第一道例题…处理一对情侣的话直接二分图染色就可以啦…但是应该如何处理那要求任意连续三人至少有两种食物呢…这道题的话根据何思齐学长的解释就是先把每对情侣连边…然后把 $2 k + 1$ 与 $2 k + 2$ 连边…为什么这样做是可行的呢…大概想一下就是如果这样连边之后如果出现了环…那么这个环的点数都是偶数的…于是我们就只需要在这样的图上进行二分图染色就可以了…我似乎忘了二分图染色怎么写借鉴了一下何思齐学长的代码…

参考代码：

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define DB double
#define SG string
using namespace std;
const int Max=1e7+5;
const int Mod=1e9+7;
const int Mx=1e5+5;
struct Node{
	int A,B;
}CP[Mx];
int N,Mark=1,Vis[Max],Col[Max];
int Cnt,To[Max],Next[Max],Head[Max];
inline int Read(){
	int X=0;char CH=getchar();bool F=0;
	while(CH>'9'||CH<'0'){if(CH=='-')F=1;CH=getchar();}
	while(CH>='0'&&CH<='9'){X=(X<<1)+(X<<3)+CH-'0';CH=getchar();}
	return F?-X:X;
}
inline void Write(int X){
	if(X<0)X=-X,putchar('-');
	if(X>9)Write(X/10);
	putchar(X%10+48);
}
void Insert(int X,int Y){
	To[++Cnt]=Y;Next[Cnt]=Head[X];Head[X]=Cnt;
}
void BFS(int Start){
	int I=0,J=1,K;
	Vis[1]=Start,Col[Start]=1;
	while(I<J){
		I++;
		int Cur=Vis[I];
		for(K=Head[Cur];K;K=Next[K]){
			int Y=To[K];
			if(Col[Y]&&Col[Y]!=3-Col[Cur]){
				Mark=0;return;
			}
			if(Col[Y]){
				continue;
			}Col[Y]=3-Col[Cur];
			Vis[++J]=Y;
		}
	}
}
int main(){
	int I,J,K;
	N=Read();
	for(I=1;I<=N;I++){
		CP[I].A=Read(),CP[I].B=Read();
		Insert(CP[I].A,CP[I].B);
		Insert(CP[I].B,CP[I].A);
	}
	for(I=1;I<=2*N;I+=2){
		Insert(I,I+1);Insert(I+1,I);
	}
	for(I=1;I<=2*N&&Mark;I++){
		if(Col[I]){
			continue;
		} else {
			BFS(I);
		}
	}
	if(!Mark){
		puts("-1");
	} else {
		for(I=1;I<=N;I++){
			Write(Col[CP[I].A]),putchar(' ');
			Write(Col[CP[I].B]),putchar('n');
		}
	}
	return 0;
}