Codeforces 405E Graph Cutting
2024-08-29 10:19:48
不会写。。
dfs的过程中把回边丢到它的祖先中去, 回溯的时候两两配对。感觉好神奇啊。
#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ull unsigned long long using namespace std; const int N = 1e5 + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + ;
const double eps = 1e-;
const double PI = acos(-); int n, m;
bool vis[N];
vector<int> G[N];
queue<int> que[N];
vector<pair<int, PII>> ans; void dfs(int u, int fa) {
vis[u] = true;
for(auto& v : G[u]) {
if(!vis[v]) {
dfs(v, u);
} else if(v != fa && vis[v]) {
que[v].push(u);
}
}
while(SZ(que[u]) >= ) {
int x = que[u].front(); que[u].pop();
int y = que[u].front(); que[u].pop();
ans.push_back(mk(x, mk(u, y)));
}
if(SZ(que[u])) {
if(!fa) {
puts("No solution");
exit();
}
int x = que[u].front(); que[u].pop();
ans.push_back(mk(x, mk(u, fa)));
} else {
que[fa].push(u);
}
} int main() {
scanf("%d%d", &n, &m);
for(int i = ; i <= m; i++) {
int u, v; scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
if(m & ) puts("No solution");
else {
dfs(, );
for(auto& t : ans)
printf("%d %d %d\n", t.fi, t.se.fi, t.se.se);
}
return ;
} /*
*/
最新文章
- hibernate缓存(一级缓存、二级缓存)
- ecmall中static变量的使用-model模型代码设计
- sql 语句累积
- 戴维&#183;卡梅伦(David William Donald Cameron)经典语录
- Palindrome Partitioning II
- 使用ttXactAdmin、ttSQLCmdCacheInfo、ttSQLCmdQueryPlan获取SQL相关具体信息[TimesTen运维]
- shell脚本练习(短路练习)
- 设计模式入门之桥接模式Bridge
- Spring与Hibernate整合中,使用OpenSessionInViewFilter后出现sessionFactory未注入问题
- C# using
- monkey测试样例
- 移动端点击事件300ms延迟问题解决方案——fastclick.js
- vue-router beforeEach死循环
- shell编程:if语句
- Ubuntu 12.04常用快捷键
- MyEclipse9.0激活步骤
- SVN库迁移整理方法----官方推荐方式
- Group By 和Having总结
- DE4加DVI子板实现静态图片显示
- SharePoint 2013 - Designer Workflow
热门文章
- 洛谷P2605 基站选址
- 【LOJ#10064】黑暗城堡
- Java基础-配置开发环境-安装JDK
- python3中__get__,__getattr__,__getattribute__的区别
- CSS reset--(来自网易)
- html5 canvas 弧形描边渐变
- javascript构造函数强制使用new
- 五行代码终极完美解决从IE6到Chrome所有浏览器的position:fixed;以及闪动问题
- 20155216 2016-2017-2 《Java程序设计》第八周学习总结
- JavaScript 计时