CodeForce 741C. Arpa’s overnight party and Mehrdad’s silent entering

题目链接

https://codeforces.com/contest/741/problem/C
CodeForce 741C. Arpa’s overnight party and Mehrdad’s silent entering
CodeForce 741C. Arpa’s overnight party and Mehrdad’s silent entering

题意

有\(n\)对情侣(\(2n\)个人)围成一圈坐在桌子边上,每个人占据一个位子,要求情侣不能吃同一种食物,并且桌子上相邻的三个人的食物必须有两个人是不同的,只有两种食物(\(1\)或者是\(2\)),问一种可行分配方式。

思路

• 如果我们能把不能吃同一种食物的人连边,问题就变成二分图黑白染色
• 所以情侣关系等价于两者之间连一条边
•"每连续的三个人不能都一样"怎么办?
• 让第\(2i\)个人和第\(2i+1\)个人不能吃一样的食物即可(即\(1\)连\(2\),\(3\)连\(4\),\(5\)连\(6\)以此类推)
• 这样肯定是个二分图——\(2i\)和\(2i-1\)分别连了他两的情侣,情侣有分别连他两的一个邻居……
每次都是给这个可能存在的环加两个点,所以有环就一定是奇环

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 50;
vector<int> G[maxn];
int c[maxn];
void add(int u, int v){
    G[v].push_back(u);
    G[u].push_back(v);
}
bool dfs(int v, int color){
    c[v] = color;
    for(auto u : G[v]){
        if(c[u] == color) return false;
        if(c[u] == 0 && !dfs(u, 3 - color)) return false;
    }
    return true;
}
void init(int n){
    for(int i = 0;i <= n;i++){
        c[i] = 0;
    }
    for(int i = 1;i <= n;i++) if(!c[i]) dfs(i, 1);
}
int a[maxn], b[maxn];
int main()
{
    std::ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for(int i = 1;i <= n;i++){
        cin >> a[i] >> b[i];
        add(a[i], b[i]);
    }
    for(int i = 2;i <= 2 * n;i += 2){
        add(i, i - 1);
    }
    init(2 * n);
    for(int i = 1;i <= n;i++){
        cout << c[a[i]] << " " << c[b[i]] << endl;
    }
    return 0;
}


上一篇:排序算法05------------------------堆排序(图解)


下一篇:玩转Zynq连载44——[ex63] MT9V034摄像头的图像平滑处理