【题解】「COCI 2018.10」Teoreti?ar
2022/9/3 6:25:06
本文主要是介绍【题解】「COCI 2018.10」Teoreti?ar,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
传送门
题目大意
有一个二分图,构造一种对边的染色方案,使得没有两个颜色相同的边共顶点。
假设对于给定二分图的答案是 \(C\),记 \(X\) 是大于等于 \(C\) 的最小的 \(2\) 的整次幂,你只需要给出一个方案,使得颜色数量不多于 \(X\)。
\(L, R\le 10^5, m\le 5\times 10^5\)
题解
设度数最大的点的度数为 \(D\),那么显然答案 \(C\ge D\),也就是说我们只要构造出一种要颜色数不超过 \(2^{\lceil \log_2 D \rceil}\) 的方案。
假设我们有一个边集 \(E\),如果每个点的度数都 \(\le 1\),那么显然此时答案为 \(1\),否则我们可以考虑把这个边集划分为两个边集 \(E_1, E_2\),使得每个点的度数尽量被平分,即都不超过 \(\lceil\frac D2\rceil\)。
这样递归下去,可以发现我们就能满足限制了。
边的分割可以跑欧拉回路(其中需要适当加虚点和虚边使得每个点的度数都为偶数)。
时间复杂度 \(O(m\log m)\)。
Code
#include <bits/stdc++.h> #define FOR(i,j,k) for(int i=j; i<=k; ++i) #define ROF(i,j,k) for(int i=j; i>=k; --i) inline int read (void) { int x = 0, f = 1, ch = getchar(); while(!isdigit(ch)) { if(ch == '-') f = -f; ch = getchar(); } while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } const int maxn = 200005; const int maxm = 500005; struct Node { int x, y, id; }; int n, m, col, ans[maxm]; std::vector <std::pair <int, int> > edge[maxn]; int lst=2, sz[maxn], Flag[maxm + maxn]; void dfs (int x, int pre=0) { while(sz[x]) { std::pair <int, int> cur = edge[x].back(); edge[x].pop_back(); -- sz[x]; if(Flag[cur.second]) continue; Flag[cur.second] = 1; dfs (cur.first, cur.second); } Flag[pre] = lst ^= 1; } void solve (std::vector <Node> v) { std::vector <int> node; for(auto&it:v) { ++ sz[it.x]; ++ sz[it.y]; node.push_back(it.x); node.push_back(it.y); edge[it.x].push_back(std::make_pair(it.y, it.id)); edge[it.y].push_back(std::make_pair(it.x, it.id)); } bool flag = 1; for(auto&it:node) if(sz[it] > 1) flag = 0; if(flag) { ++ col; for(auto&it:v) ans[it.id] = col; for(auto&it:node) edge[it].clear(), sz[it] = 0; return ; } int cnt = m; for(auto&it:node) if(sz[it]&1) { ++ cnt; ++ sz[it]; ++ sz[n + 1]; edge[it].push_back(std::make_pair(n + 1, cnt)); edge[n + 1].push_back(std::make_pair(it, cnt)); } lst = 2; dfs (n + 1); for(auto&it:node) dfs (it); std::vector <Node> V[2]; FOR(i,m+1,cnt) Flag[i] = 0; for(auto&it:v) { V[Flag[it.id] == 2].push_back(it); Flag[it.id] = 0; } solve (V[0]); solve (V[1]); } int main (void) { int l = read(), r = read(); m = read(); std::vector <Node> edge; n = l + r; FOR(i,1,m) { int x = read(), y = read(); edge.push_back((Node) {x, l + y, i}); } solve (edge); printf("%d\n", col); FOR(i,1,m) printf("%d\n", ans[i]); return 0; }
这篇关于【题解】「COCI 2018.10」Teoreti?ar的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升
- 2024-05-08代码报错不用愁,CodeGeeX一键完成代码修复、错误解释的功能上线了!