Graph Cutting

不会写。。

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 ;
} /*
*/

最新文章

  1. hibernate缓存(一级缓存、二级缓存)
  2. ecmall中static变量的使用-model模型代码设计
  3. sql 语句累积
  4. 戴维&#183;卡梅伦(David William Donald Cameron)经典语录
  5. Palindrome Partitioning II
  6. 使用ttXactAdmin、ttSQLCmdCacheInfo、ttSQLCmdQueryPlan获取SQL相关具体信息[TimesTen运维]
  7. shell脚本练习(短路练习)
  8. 设计模式入门之桥接模式Bridge
  9. Spring与Hibernate整合中,使用OpenSessionInViewFilter后出现sessionFactory未注入问题
  10. C# using
  11. monkey测试样例
  12. 移动端点击事件300ms延迟问题解决方案——fastclick.js
  13. vue-router beforeEach死循环
  14. shell编程:if语句
  15. Ubuntu 12.04常用快捷键
  16. MyEclipse9.0激活步骤
  17. SVN库迁移整理方法----官方推荐方式
  18. Group By 和Having总结
  19. DE4加DVI子板实现静态图片显示
  20. SharePoint 2013 - Designer Workflow

热门文章

  1. 洛谷P2605 基站选址
  2. 【LOJ#10064】黑暗城堡
  3. Java基础-配置开发环境-安装JDK
  4. python3中__get__,__getattr__,__getattribute__的区别
  5. CSS reset--(来自网易)
  6. html5 canvas 弧形描边渐变
  7. javascript构造函数强制使用new
  8. 五行代码终极完美解决从IE6到Chrome所有浏览器的position:fixed;以及闪动问题
  9. 20155216 2016-2017-2 《Java程序设计》第八周学习总结
  10. JavaScript 计时