HDU - 6311 Cover(无向图的最少路径边覆盖 欧拉路径)

题意

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

分析

首先联通块之间是独立的,对于一个联通块内,最少路径覆盖就是  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 ;
}
上一篇:sicily 1010. 单词数值


下一篇:详解SQL Server 2005 Express下的事件探查器