DDOSvoid's Blog

CF 547D Mike and Fish

发表于 分类于
本文字数： 1.4k 阅读时长 ≈ 1 分钟

题目描述

http://codeforces.com/contest/547/problem/D

简要题意：现在有 $n$ 个点 $(x_i,y_i)$，要求将每个点染成红色或者蓝色，且横坐标相同的点中蓝色和红色点的数量相差不超过 $1$，纵坐标同理

$n\le 2\times 10^5$

Solution

我们考虑将横坐标和纵坐标看成图中的点，如果有一个点 $(x,y)$，我们就连一条 $x$ 到 $y$ 的无向边

现在我们需要染色，这相当于给无向边定向，且定向之后需要保证每个点的入度和出度的差的绝对值不超过 $1$，如果要求入度等于出度的话，我们容易想到欧拉回路，但现在是要求入度和出度的绝对值不超过 $1$

我们考虑将其转化为入度等于出度的情况，注意到图中度数为奇数的点一定有偶数个，那么我们新建一个点，将所有奇数点连向这个点，然后再跑欧拉回路就行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#define maxn 400010
using namespace std;

const int N = 200000;

int n, m;

struct Edge {
    int to, next, k;
    bool ext;
} e[maxn * 2]; int c1, head[maxn], du[maxn];
inline void add_edge(int u, int v, int k) {
    e[c1].to = v; e[c1].k = k; 
    e[c1].next = head[u]; head[u] = c1++;
}

int ans[maxn];
void dfs(int u) {
    for (int &i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to, k = e[i].k; bool &ext = e[i].ext, &Ext = e[i ^ 1].ext;
        if (ext) continue; ext = Ext = 1; dfs(v);
        if (u <= N || v > N) ans[k] = 1;
        else if (u > N || v <= N) ans[k] = 0; 
    }
} 

int main() { fill(head, head + maxn, -1); 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int x, y; cin >> x >> y;
        add_edge(x, y + N, i); add_edge(y + N, x, i);
        ++du[x]; ++du[y + N];
    } int rt = 2 * N + 1;
    for (int i = 1; i <= 2 * N; ++i)
        if (du[i] & 1) add_edge(i, rt, 0), add_edge(rt, i, 0);
    for (int i = 1; i <= 2 * N; ++i) dfs(i);
    for (int i = 1; i <= n; ++i) cout << (ans[i] ? 'b' : 'r'); cout << "\n";
    return 0;
}