「CF547D」 Mike and Fish

传送门

介绍三种做法。

---

\(\texttt{Solution 1}\) 上下界网络流

我们将每一行、每一列看成一个点。

两种颜色的数量最多相差 \(1\)，即红点的个数和蓝点个数范围都在 \([\lfloor \frac{cnt}{2}\rfloor,\lceil \frac{cnt}{2}\rceil]\) 当中。

若有一个点 \((x,y)\)，则从第 \(x\) 行向第 \(y\) 列连边，容量为一。若有流量，则为红点，否则为蓝点。

最后从源点向行连边，从列向汇点连边，跑一边有源汇上下界可行流即可。

---

\(\texttt{Solution 2}\) 二分图染色

我们将同一行的点两两配对，将同一列的点两两配对，其形成一定是一个二分图。

考虑证明：每个点最多连出两条边：横边和竖边。而由此易证得这张图上的环一定是横竖边交替排列的，即所有的环都为偶环。

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

（是真的妙啊）

贴代码

/*---Author:HenryHuang---*/

/*---Never Settle---*/

#include<bits/stdc++.h>

#define add(a,b) e[a].emplace_back(b)

using namespace std;

const int maxn=2e5+5;

int lstx[maxn],lsty[maxn];

int col[maxn];

vector<int> e[maxn];

void dfs(int u,int co){

	col[u]=co;

	for(auto v:e[u])

		if(col[v]==-1)

			dfs(v,co^1);

}

int main(){

	ios::sync_with_stdio(0);

	cin.tie(0),cout.tie(0);

	int n;cin>>n;

	for(int i=1;i<=n;++i) col[i]=-1;

	for(int i=1;i<=n;++i){

		int x,y;cin>>x>>y;

		if(lstx[x]){

			add(lstx[x],i),add(i,lstx[x]);

			lstx[x]=0;

		}

		else lstx[x]=i;

		if(lsty[y]){

			add(lsty[y],i),add(i,lsty[y]);

			lsty[y]=0;

		}

		else lsty[y]=i;

	}

	for(int i=1;i<=n;++i) if(col[i]==-1) dfs(i,0);

	for(int i=1;i<=n;++i) cout<<(col[i]?"r":"b");

	return 0;

}

---

\(\texttt{Solution 3}\) 欧拉回路

将横纵坐标之间连边，问题转化为对每条边定向使得每个点的入度和出度最多相差 \(1\)。

这和 CF527E 很像，只是有一个最多相差 \(1\) 的条件。

考虑若一个点度数为偶数，则其入度和出度必然相等。

所以我们考虑如何处理一个点度数为奇数的情况。

我们新建一些虚边，将这些奇点两两配对，然后跑欧拉回路即可。