题意

给个无向图,无重边和自环,问最少需要多少路径把边覆盖了。并输出相应路径

分析

首先联通块之间是独立的,对于一个联通块内,最少路径覆盖就是  max(1,度数为奇数点的个数/2)。然后就是求欧拉路径了,先将块内度数为奇数的点找出来,留下两个点,其余两两连上虚边,这样我们选择从一个奇数点出发到另一个奇数点,求出一条欧拉路径,统计总路径数。接着就dfs,注意一些细节。

附赠一个求欧拉回路的fleury算法:https://blog.csdn.net/u011466175/article/details/18861415

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <set>
#include <bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(a, b) memset(a, b, sizeof(a))
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define eps 0.0000000001
#define IOS ios::sync_with_stdio(0);cin.tie(0);
#define random(a, b) rand()*rand()%(b-a+1)+a
#define pi acos(-1)
const ll INF = 0x3f3f3f3f3f3f3f3fll;
const int inf = 0x3f3f3f3f;
const int maxn = + ;
const int maxm = + ;
const int mod = 1e9+; struct ND{
int v,nxt;
ND(){}
ND(int _v,int _nxt):v(_v),nxt(_nxt){}
}e[maxn*];
bool pvis[maxn],evis[maxn*];
int head[maxn],du[maxn],tot;
int n,m,cnt;
vector<int> ans[maxn],odd;
void init(){
cnt=tot=;
memset(head,-,sizeof(head));
memset(du,,sizeof(du));
memset(pvis,false,sizeof(pvis));
memset(evis,false,sizeof(evis));
for(int i=;i<=n;i++) ans[i].clear();
}
void addedge(int u,int v){
e[tot]=ND(v,head[u]);head[u]=tot++;
e[tot]=ND(u,head[v]);head[v]=tot++;
}
void dfs1(int u){
pvis[u]=true;
if(du[u]%) odd.push_back(u);//同一联通块里奇数度的点
for(int i=head[u];~i;i=e[i].nxt){
int v = e[i].v;
if(!pvis[v]){
dfs1(v);
}
}
}
void dfs2(int u){
for(int i=head[u];~i;i=e[i].nxt){
int v=e[i].v;
if(!evis[i]){
evis[i]=evis[i^]=true;//判断边有没有走过
dfs2(v);
int tmp=i%?-(i+)/:i/+; //对应边的编号
if(i<*m) ans[cnt].push_back(tmp); //为原先存在的边
else cnt++; //新连的虚边
}
}
}
int main(){
#ifdef LOCAL
freopen("in.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
while(~scanf("%d%d",&n,&m)){
init();
int u,v;
for(int i=;i<m;i++){
scanf("%d%d",&u,&v);
addedge(u,v);
du[u]++,du[v]++;
}
for(int i=;i<=n;i++){
if(!pvis[i]&&du[i]){
odd.clear();
dfs1(i);
for(int i=;i<odd.size();i+=){//保留两个奇度点,其余两两连边
addedge(odd[i],odd[i+]);
}
int rt = odd.size()?odd[]:i;
dfs2(rt);
cnt++;
}
}
printf("%d\n",cnt);
for(int i=;i<cnt;i++){
printf("%d",ans[i].size());
for(int j=ans[i].size()-;j>=;j--){
printf(" %d",ans[i][j]);
}puts("");
}
} return ;
}

最新文章

  1. uwp如何建立任何形状的头像,如圆形,方形,六边形等
  2. 了解 Office 365
  3. Devexpress GridView内嵌dx:ASPxGridLookup取得控件值乱跳解决方案
  4. Asp.Net:GridView 编辑、删除、自定义分页以后备用
  5. iOS检测网络连接状态
  6. CodeForces 173B Chamber of Secrets 二分图+最短路
  7. java客户端连接MongoDB数据库的简单使用
  8. (三)phpcms之文件目录
  9. angular.forEach
  10. [Regular Expressions] Find the Start and End of Whole Words
  11. 黑马程序员 Java基础&lt;九&gt;---&gt; 多线程
  12. GCD实现简单的单例类-Singletion
  13. fn标签
  14. HDU 6185 Covering 矩阵快速幂
  15. Dynamics CRM 打开数据加密报错及修改用户邮件保存报错的解决方法
  16. Mac os x下几款mysql客户端
  17. android studio出现offline情况
  18. HTTP的基本原理
  19. 自定义Markdown例子
  20. LOJ500 ZQC的拼图 二分答案、DP

热门文章

  1. codeforces 997C.Sky Full of Stars
  2. codeforces 1051F The Shortest Statement
  3. 「SDOI2014」向量集 解题报告
  4. Eclipse Memory Analyzer(MAT)使用
  5. Codeforces Round #508 (Div. 2) C D
  6. js 判断数据是否为空
  7. python面向对象中的一些特殊__方法__
  8. cnblogs latex公式
  9. linux系统调用之网络管理1
  10. linux 系统调用之文件操作