sgu 286. Ancient decoration（最小环覆盖） - c++编程基础

TOP

sgu 286. Ancient decoration（最小环覆盖）

2014-11-23 21:38:18 来源: 作者: 【大中小】浏览:6次

给你一个n个点，每个点度为k（k为偶数）的无向图，问是否能将图中的n条边染色，使得每个点都拥有两条被染色的边。也就是说，是否存在拥有原图中n条边的子图，使得每个点的度为2？仔细想想，每个点的度为2，实际上就是求原图的最小环覆盖了。

求最小环覆盖的方法就是先求出原图的有向欧拉回路（k为偶数，欧拉回路必然存在），然后问题就转化成了是否能选择欧拉回路中的n条边，使得所有点都被覆盖？这不就转化成了DAG的最小路径覆盖了么！

#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#define FF(i, a, b) for(int i=a; i=b; i--)  
#define REP(i, n) for(int i=0; i


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：串的模式匹配――Brute-Force算法	下一篇： poj 3269 Building A New Barn

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: