当前位置: 首页 > news >正文

CF2150F Cycle Closing

感觉上判是否能一次完成是困难的。设两次的路径长度分别为 \(a, b\),考虑一些特殊情况。

题目一定有解,考虑取出一棵生成树。可以发现,第二次操作时的边数实际上很多,感觉上对于 \(b\) 不能限制得太小。考虑 \(a\) 较小的情况。

事实上我们想解决的是如下问题:选定一个 \(b\),对于任意的 \((s,t)\),要么 \(\operatorname{dist}(s,t)=1\)\(a\),要么从 \(s\),每次走 \(1\)\(a\) 的距离,能够恰好 \(b\) 步到达 \(t\)

对于 \(a=3\),可以发现每步一定会改变深度奇偶性,因此步数的奇偶性确定了,不太能做。而如果 \(a\ge 4\),路径形态比较复杂。因此考虑 \(a=2\) 的情形。

首先 \(b\) 有一个下界为 \(\lceil\frac{D+1}{2}\rceil\),其中 \(D\) 为直径长度。事实上我们也能构造出 \(b=D\) 的方案。

考虑一条链 \(s\to t\),其长度为 \(d\)

如果 \(d\ge D\),那么我们在这条链上不停跳 \(=2\) 的距离,然后一段后缀一步步走即可。

如果 \(d<D\),此时我们找出距离 \(s\) 最远点 \(x\),设 \(x\)\(s\to t\) 的最近点为 \(p\),那么 \(s\to t\) 上的边还是一步步走,然后再在 \(p\to x\) 这条链上通过 \(1\to 3\to\cdots 2k+1\to 2k\to \cdots\to 2\) 状物消耗剩余步数即可。

#include <bits/stdc++.h>
using namespace std;const int kN = 205;
int n, m;
bool vis[kN];
bool e[kN][kN];
vector<int> tr[kN];
vector<int> path[kN][kN];void DFS(int x) {vis[x] = 1;for(int to = 1; to <= n; to++) {if(vis[to] || !e[x][to]) continue;tr[x].push_back(to);tr[to].push_back(x); DFS(to);}
}void DFS2(int x, int fa, vector<int> v, int rt) {v.push_back(x);path[rt][x] = v;for(int to : tr[x]) {if(to != fa) DFS2(to, x, v, rt);}
}void Clear() {memset(vis, 0, sizeof(vis));memset(e, 0, sizeof(e));fill_n(tr, n + 3, vector<int> {});for(int i = 1; i <= n; i++) {fill_n(path[i], n + 3, vector<int> {});}
}void Solve() {cin >> n >> m;Clear();for(int i = 1; i <= m; i++) {int u, v;cin >> u >> v;e[u][v] = e[v][u] = 1;}DFS(1);for(int i = 1; i <= n; i++) {DFS2(i, 0, vector<int> {}, i);}int x = 0, y = 0, dia = -1;for(int i = 1; i <= n; i++) {for(int j = i + 1; j <= n; j++) {int len = path[i][j].size() - 1;if(dia < len) dia = len, x = i, y = j;}}cout << "2\n";{vector<tuple<int, int, int>> edge;for(int i = 1; i <= n; i++) {for(int j = i + 1; j <= n; j++) {if(e[i][j]) continue;for(int k = 1; k <= n; k++) {if(e[k][i] && e[k][j]) {edge.emplace_back(i, k, j);break;}}}}cout << "3\n";cout << edge.size() << "\n";for(auto k : edge) {int x, y, z;tie(x, y, z) = k;cout << x << " " << y << " " << z << "\n";e[x][z] = e[z][x] = 1;}}int len = (dia + 1) / 2;vector<vector<int>> ans;for(int i = 1; i <= n; i++) {for(int j = i + 1; j <= n; j++) {if(e[i][j]) continue;int dis = path[i][j].size() - 1;vector<int> p;if(dis >= len) {for(int k = 0; k <= dis; k += 2) {p.push_back(path[i][j][k]);if(p.size() + (dis - k) == len + 1) {while(k < dis) p.push_back(path[i][j][++k]);break;}}ans.push_back(p);continue;}if(path[i][x].size() < path[i][y].size()) swap(x, y);int nd = len - dis, t = 0;while((t + 1 < path[i][j].size()) && (path[i][j][t + 1] == path[i][x][t + 1])) t++;if(path[i][x][1] != path[i][j][1]) {p.push_back(i);vector<int> v = path[i][x];for(int k = 2; k <= nd; k += 2) {p.push_back(v[k]);}for(int k = nd - !(nd & 1); k >= 1; k -= 2) {p.push_back(v[k]);}for(int k = 1; k < path[i][j].size(); k++) {p.push_back(path[i][j][k]);}}else {for(int k = 0; k < t; k++) {p.push_back(path[i][j][k]);}vector<int> v;for(int k = t; k < path[i][x].size(); k++) {v.push_back(path[i][x][k]);}for(int k = 1; k <= nd; k += 2) {p.push_back(v[k]);}for(int k = nd - (nd & 1); k >= 1; k -= 2) {p.push_back(v[k]);}for(int k = t; k < path[i][j].size(); k++) {p.push_back(path[i][j][k]);}}ans.push_back(p);}}cout << len + 1 << "\n";cout << ans.size() << "\n";for(vector<int> v : ans) {for(int i : v) cout << i << " ";cout << "\n";}
}int main() {
//  freopen("1.in", "r", stdin);
//  freopen("1.out", "w", stdout);ios::sync_with_stdio(0), cin.tie(0);int t;cin >> t;while(t--) Solve();return 0;
}
http://www.hskmm.com/?act=detail&tid=26979

相关文章:

  • Easysearch 字段隐身之谜:source_reuse 与 ignore_above 的陷阱解析
  • QOJ856 Cactus 广义串并联图
  • CF2152 订题
  • 静态路由
  • Kruskal 重构树学习笔记
  • GJ Round 2025赛季
  • ASP.NET Core 中读取 UserAgent 的正确姿势
  • vLLM推理加速指南:7个技巧让QPS提升30-60%
  • Git学习记录(二):代码patch
  • 2025年10月化妆品代工厂最新推荐排行榜:聚焦 OEM/ODM/ 网红爆款需求,精选优质企业助品牌高效合作
  • Exchange安全漏洞分析:ProxyOracle攻击链详解
  • 牛客 周赛111 20251008
  • 本人于2025上半学期编码需要遵守的规范(参考腾讯内部编码规范)
  • 10.8 CSP-JS 模拟赛 T5. xor
  • 防抖 解释
  • 从零到一搭建:vue3+vite7+antfu+stylelint+githooks,全流程配置,附带源码,集成css变量使用,下载即用
  • bat批处理脚本文件-获取当前时间的几种方法
  • 二分图最大权完美匹配 KM算法
  • 2025.10.8模拟赛
  • Python 中的排序排序函数及区别
  • RL | 速读 IJCAI 2025 的强化学习论文
  • IDM弹窗解决 - -一叶知秋
  • PHP+MySQL开发语言 在线下单订水送水小脚本源码及搭建指南
  • Sliding Window Algorithm
  • 国庆模拟赛总结
  • 深入解析:video-audio-extractor:视频转换为音频
  • 10.8 CSP-JS 模拟赛 T4. discover
  • 20251008 模拟测 总结
  • VuePress v2是否支持Vue2的配置?
  • 新人UP主:晓牛开发者的第一篇自我介绍博客测试发布