首页 > 代码库 > UESTC 1634 记得小苹初见,两重心字罗衣
UESTC 1634 记得小苹初见,两重心字罗衣
题意:给你不超过20万个点,要求每行每列的蓝红数量不能相差超过一,输出一种方案
题解:解法1:每一个棋子看做一个点,每一列任意两个点连接一条边,同理,每一行也连两条边,DFS染色就可以
解法2:每一个棋子的横坐标和纵坐标连接一条边,也就是对边染色,二分图?这里可以发现,其实是一笔画问题,找到一条路进行交替染色就可以,不满足欧拉回路就将奇数度数的边连到一个新的点使得图成为欧拉回路
#include <bits/stdc++.h>#pragma comment(linker, "/STACK:102400000,102400000")#define maxn 200000using namespace std;struct edge{ int to, num;};vector<edge >G[maxn*2+10];int mark[maxn*4+10], col=0, n;inline void dfs(int x){ while(!G[x].empty()){ edge t = G[x].back(); G[x].pop_back(); if(mark[t.num] == -1){ col ^= 1; mark[t.num] = col; dfs(t.to); } }}int main(){ int a,b,num; cin>>n; for(int i=0;i<n;i++){ cin>>a>>b; G[a].push_back((edge){b+maxn, i}); G[b+maxn].push_back((edge){a, i}); } num = n; for(int i=1;i<=maxn*2;i++) if(G[i].size()%2 == 1){ G[i].push_back((edge){0, num}); G[0].push_back((edge){i, num++}); } memset(mark, -1, sizeof(mark)); for(int i=0;i<=maxn;i++) if(!G[i].empty()) dfs(i); for(int i=0;i<n;i++) cout<<(mark[i]?‘r‘:‘b‘); cout<<endl; return 0;}
UESTC 1634 记得小苹初见,两重心字罗衣
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。