cf550 D. Regular Bridge
2022/6/6 23:23:02
本文主要是介绍cf550 D. Regular Bridge,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题意:
给定 \(k\),构造连通、无重边、无自环、每个点的度为 \(k\) 且含至少一个桥的无向无权图
\(1\le k \le 100\)
思路:
当 \(k\) 为偶数时无解:设 \(k=2s\),设某连通块 \(G\) 与图的其他部分通过桥 \(e\) 连接,去掉桥 \(e\),则 \(G\) 中有一个点的度为 \(2s-1\),其他点的度为 \(2s\)。则 \(G\) 中所有点的总度数为奇数,根据握手定理这是不可能的。
当 \(k\) 为奇数时一定有解。这样构造:
一共 \(2k+4\) 个点,两个连通块,每个连通块中有 \(2k+4\) 个点。
考虑第一个连通块,其中的点编号为 \(1\sim k+2\)
第一个连通块中的点分为三种:\(1\) 号点、\(2\sim k\) 号点、\(k+1\) 和 \(k+2\) 两点
\(1\) 号点与另一个连通块相连,然后与 \(2\sim k\) 号点相连;
\(k+1\) 号点与 \(2\sim k\) 号点相连,\(k+2\) 号也是。然后把 \(k+1\) 和 \(k+2\) 连起来;
\(2\sim k\) 号点两两相连,但是删除形如 “\(i -i+1\),$i $ 为偶数” 的边
int k; vector<PII> edges; void make(int base) { // 1, 2~k, k+1,k+2 for(int i = 2; i <= k; i++) edges.pb({1+base,i+base}), edges.pb({k+1+base,i+base}), edges.pb({k+2+base,i+base}); for(int i = 2; i < k; i++) for(int j = i + 1; j <= k; j++) if(!(j - i == 1 && j % 2)) edges.pb({i+base,j+base}); edges.pb({k+1+base,k+2+base}); } void sol() { cin >> k; if(k % 2 == 0) return cout << "NO", void(); if(k == 1) return cout << "YES\n2 1\n1 2", void(); cout << "YES\n" << 2*k+4 << ' '; edges.pb({1,k+3}); make(0), make(k+2); cout << edges.size() << endl; for(auto &[x,y]: edges) cout << x << ' ' << y << endl; }
这篇关于cf550 D. Regular Bridge的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 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功能效果提升