Codeforces 547D Mike and Fish

本文主要是介绍Codeforces 547D Mike and Fish，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

把横纵坐标坐标建二分图，每个原图上的点连边，如果所有的点度数都是偶数，求出欧拉回路，把这条路径交替染色就可以了。
在两边各建一个虚拟结点，如果有点的度数是奇数，把它跟另一侧的虚拟结点连边。如果虚拟结点度数是奇数，也把它们之间连边。这样图中所有点的度数都是偶数，可以求出欧拉回路染色。而对于每个加了新边的点，它只加了一条边，因此对于他来说两种颜色最多差 1 <script id="MathJax-Element-5" type="math/tex">1</script>。

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=2000010;
int xx[maxn],yy[maxn],ord[maxn],vis[maxn],v[maxn],sta[maxn],ans[maxn],n,mx,my,top;
vector<pair<int,int> > to[maxn];
vector<pair<int,int> >::iterator it[maxn];
void dfs(int u)
{vis[u]=1;while (it[u]!=to[u].end()){pair<int,int> pr=*it[u];++it[u];if (!v[pr.second]){v[pr.second]=1;dfs(pr.first);sta[++top]=pr.second;}}
}
int main()
{//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);int num;scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d%d",&xx[i],&yy[i]);for (int i=1;i<=n;i++) ord[i]=xx[i];sort(ord+1,ord+n+1);mx=unique(ord+1,ord+n+1)-ord-1;for (int i=1;i<=n;i++) xx[i]=lower_bound(ord+1,ord+mx+1,xx[i])-ord;for (int i=1;i<=n;i++) ord[i]=yy[i];sort(ord+1,ord+n+1);my=unique(ord+1,ord+n+1)-ord-1;for (int i=1;i<=n;i++) yy[i]=lower_bound(ord+1,ord+my+1,yy[i])-ord;for (int i=1;i<=n;i++){to[xx[i]].push_back(make_pair(yy[i]+mx+1,i));to[yy[i]+mx+1].push_back(make_pair(xx[i],i));}num=n;for (int i=1;i<=mx;i++)if (to[i].size()&1){num++;to[i].push_back(make_pair(mx+my+2,num));to[mx+my+2].push_back(make_pair(i,num));}for (int i=1;i<=my;i++)if (to[i+mx+1].size()&1){num++;to[i+mx+1].push_back(make_pair(mx+1,num));to[mx+1].push_back(make_pair(i+mx+1,num));}if (to[mx+1].size()&1){num++;to[mx+1].push_back(make_pair(mx+my+2,num));to[mx+my+2].push_back(make_pair(mx+1,num));}for (int i=1;i<=mx+my+2;i++) it[i]=to[i].begin();for (int i=1;i<=mx+my+2;i++)if (!vis[i]){top=0;dfs(i);for (int j=1;j<=top;j++)ans[sta[j]]=j&1;}for (int i=1;i<=n;i++)if (ans[i]) putchar('b');else putchar('r');
}

这篇关于Codeforces 547D Mike and Fish的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---