CF 547D. Mike and Fish 题解

Solution 1 二分图染色

显然这题是构造染色方案，于是我们考虑将矩阵转化成图进行染色。

结论：将同一行的点两两配对，将同一列的点两两配对，形成的一定是二分图。

证明：由于每个点最多连出一条横边和一条竖边，那么这张图上的环一定是横竖边交替排列的，即所有的环都为偶环。

所以我们对这张二分图进行黑白染色，每一行和每一列最多有一个点为孤立的点，符合题目要求。

想明白这题难度就远远不到 2600 了。

代码

//547D. Mike and Fish
#include <bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
int n,x[MAXN],y[MAXN],col[MAXN];
vector<int> g[MAXN];
void DFS(int u,int c)
{
    col[u]=c;
    for(int v:g[u])
    {
        if(!~col[v])
        {
            DFS(v,c^1);
        }
    }
    return;
}
int main()
{
    int tx,ty;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&tx,&ty);
        if(x[tx])
        {
            g[i].push_back(x[tx]);
            g[x[tx]].push_back(i);
            x[tx]=0;
        }
        else 
        {
            x[tx]=i;
        }
        if(y[ty])
        {
            g[i].push_back(y[ty]);
            g[y[ty]].push_back(i);
            y[ty]=0;
        }
        else 
        {
            y[ty]=i;
        }
    }
    memset(col,-1,sizeof(col));
    for(int i=1;i<=n;i++)
    {
        if(!~col[i])
        {
            DFS(i,0);
        }
    }
    for(int i=1;i<=n;i++)
    {
        printf("%c",col[i]?'r':'b');
    }
    printf("\n");
    return 0;
}
/*
 * CF
 * https://codeforces.com/contest/547/problem/D
 * C++20 -O0
 * 2022.10.5
 */

其他做法

详见 这篇博客，介绍了本题的网络流和欧拉回路做法。