网站建设丩金手指排名壹陆,什么是交互式网站,公司介绍简介,wordpress 文章查看次数题目描述#xff1a;
有n对情侣#xff08;2n个人#xff09;围成一圈坐在桌子边上#xff0c;每个人占据一个位子#xff0c;要求情侣不能吃同一 种食物#xff0c;并且桌子上相邻的三个人的食物必须有两个人是不同的#xff0c;只有两种食物#xff08;1或者是2
有n对情侣2n个人围成一圈坐在桌子边上每个人占据一个位子要求情侣不能吃同一 种食物并且桌子上相邻的三个人的食物必须有两个人是不同的只有两种食物1或者是2问一种可行分配方式。
题解
如果我们能把不能吃同一种食物的人连边问题就变成二分图黑白染色 • 所以情侣关系等价于两者之间连一条边 • “每连续的三个人不能都一样”怎么办 • 让第2i个人和第2i1个人不能吃一样的食物即可即1连23连45连6以此类推 • 这样肯定是个二分图——2i和2i-1分别连了他两的情侣情侣又分别连他两的一个邻居…… 每次都是给这个可能存在的环加两个点所以有环就一定不是奇环 蓝边表示情侣连边红边表示相邻点对隔一对连一条 基础的二分图问题
代码
#includebits/stdc.h
typedef long long ll;
using namespace std;
inline int read(){int s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9) ss*10ch-0,chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
const int maxn5e59;
vectorintedge[maxn];
int a[maxn];
int b[maxn];
int col[maxn];
int vis[maxn];
void dfs(int now,int co)
{vis[now]1;col[now]co;for(int i:edge[now]){if(!vis[i]){if(co1)dfs(i,2);else dfs(i,1); }}
}
int main()
{int n;cinn;for(int i1;in;i){cina[i]b[i];edge[a[i]].push_back(b[i]);edge[b[i]].push_back(a[i]); }for(int i1;in*2;ii2){edge[i].push_back(i1);edge[i1].push_back(i);}for(int i1;i2*n;i){if(!vis[i])dfs(i,1);}for(int i1;in;i){printf(%d %d\n,col[a[i]],col[b[i]]);}return 0;
}
