hdu6311如何求解无向图的最小路径覆盖问题？

本文共计1866个文字，预计阅读时间需要8分钟。

这道题目主要讨论的是一个算法问题。其核心是求解无向图的最小路径覆盖。简单来说，就是找到一种方式，用最少的边来覆盖图中的所有顶点。

与有向图的不同之处在于，对于有向图的最小路径覆盖，我们将其转化为求解最小欧拉路径。而在这里，我们直接求解无向图的最小路径覆盖。

欧拉图的一个结论是：如果一个图的每一条边都恰好属于一条欧拉路径，那么这个图就是一个欧拉图。在欧拉图中，欧拉路径的数量为2（如果图有偶数条边，则为偶数个欧拉路径，否则为奇数个）。因此，求解最小路径覆盖问题可以转化为寻找这些欧拉路径，并计算它们覆盖的边数。

欧拉路径的度数（即路径上的顶点数）可以用来计算最小路径覆盖的边数。欧拉路径的度数为路径上的顶点数，除以2（如果路径为偶数长，则为奇数长），得到的值就是路径覆盖的边数。因为每个顶点被计算了两次（一次进入，一次离开），所以最终结果是这个值的一半。

综上所述，这个算法的关键在于寻找图中的欧拉路径，并计算它们的覆盖边数，以实现最小路径覆盖。

这题主要是个套路。。就是求无向图最小路径覆盖。。

与有向图的二分图做法不同，这个是转化为求最少的欧拉路径。。

欧拉图有个结论是欧拉路径的个数为度为奇数的点的个数/2（可以类比欧拉回路的结论）

然后求欧拉路径的方法是fleury算法。。其思想就是暴力dfs，然后巧妙的地方就是边是方向取的，即以出栈的顺序为欧拉路径。。

然后就是一大堆细节问题。。大概是今天没什么人做出来的原因。。。

这题其实覆盖得情况比较全面（偶数的欧拉回路，奇数的欧拉回路和欧拉路径、分块求欧拉路径等），作为模板其实挺合适。。可以记下来。。

/**
*　　　　　　 　　┏┓　　 　┏┓
* 　　　　　 　　┏┛┗━━━━━━━┛┗━━━┓
* 　　　　　 　　┃　　　　　　　┃ 　
* 　　　　　 　　┃　　　━　　 　┃
* 　　　　　 　　┃　＞　　　＜　┃
* 　　　　　 　　┃　　　　　　　┃
* 　　　　　 　　┃...　⌒　... 　┃
* 　　　　　　 　┃ ┃
* 　　　　　　 　┗━┓ ┏━┛
* 　　　　　　　　　┃ ┃　Code is far away from bug with the animal protecting　　　　　　　　　　
* 　　　　　　　　　┃ ┃ 神兽保佑,代码无bug
* 　　　　　　　　　┃ ┃　　　　　　　　　　　
* 　　　　　　　　　┃ ┃ 　　　　　　
* 　　　　　　　　　┃ ┃
* 　　　　　　　　　┃ ┃　　　　　　　　　　　
* 　　　　　　　　　┃ ┗━━━┓
* 　　　　　　　　　┃ ┣┓
* 　　　　　　　　　┃ ┏┛
* 　　　　　　　　　┗┓┓┏━━━━━━━━┳┓┏┛
* 　　　　　　　　　　┃┫┫ ┃┫┫
* 　　　　　　　　　　┗┻┛ ┗┻┛
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,l,r) for(int i=l;i>=r;i--)
#define link(x) for(edge *j=h[x];j;j=j->next)
#define mem(a) memset(a,0,sizeof(a))
#define ll long long
#define eps 1e-12
#define succ(x) (1LL<<x)
#define lowbit(x) (x&(-x))
#define sqr(x) ((x)*(x))
#define mid (x+y>>1)
#define NM 100005
#define nm 400000
#define N 1000005
#define M(x,y) x=max(x,y)
const double pi=acos(-1);
const ll inf=998244353;
using namespace std;
ll read(){
ll x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return f*x;
}



struct edge{int t,v;bool f;edge*next,*rev;}e[nm],*h[NM],*o=e;
void _add(int x,int y,int v){o->t=y;o->v=v;o->next=h[x];h[x]=o++;}
void add(int x,int y,int v){_add(x,y,v);_add(y,x,-v);h[x]->rev=h[y];h[y]->rev=h[x];}
int n,m,_x,_y,cnt,b[NM],s;
bool v[NM];
vector<int>a[NM];

void dfs(int x){
v[x]=true;
link(x)if(!j->f){
j->rev->f=j->f=true;
dfs(j->t);
if(j->v==0)a[++cnt].clear();else a[cnt].push_back(-j->v);
}
}

int main(){
while(~scanf("%d%d",&n,&m)){
mem(e);mem(h);o=e;mem(b);s=0;mem(v);cnt=0;
inc(i,1,m){
_x=read();_y=read();
add(_x,_y,i);
b[_x]++;b[_y]++;
}
_x=0;
inc(i,1,n)if(b[i]&1){
if(_x)add(_x,i,0),_x=0;
else _x=i;
}
inc(i,1,n)if(!v[i]&&b[i]%2)a[++cnt].clear(),dfs(i),cnt--;
inc(i,1,n)if(!v[i]&&b[i])a[++cnt].clear(),dfs(i);
printf("%d\n",cnt);
inc(i,1,cnt){printf("%d ",m=a[i].size());inc(j,0,m-2)printf("%d ",a[i][j]);printf("%d\n",a[i][m-1]);}
//printf(":::\n");
}
return 0;
}

Cover

Time Limit: 6000/3000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 225Accepted Submission(s): 36
Special Judge

Problem Description

The Wall has down and the King in the north has to send his soldiers to sentinel.
The North can be regard as a undirected graph (not necessary to be connected), one soldier can cover one path. Today there's no so many people still breathing in the north, so the King wants to minimize the number of soldiers he sent to cover each edge exactly once. As a master of his, you should tell him how to arrange soldiers.

Input

There might be multiple test cases, no more than 20. You need to read till the end of input.
In the first line, two integers n and m, representing the number of nodes and edges in the graph.
In the following m lines, each contain two integers, representing two ends of an edge.
There are no parallel edges or self loops.
1≤n,m≤100000

Output

For each test case, the first line contains number of needed routes, p.
For the following p lines, an integer x in the beginning, followed by x integers, representing the list of used edges. Every integer should be a positive or negative integer. Its absolute value represents the number of chosen edge (1~n). If it's positive, it shows that this edge should be passed as the direction as the input, otherwise this edge should be passed in the direction different from the input. Edges should be in correct order.

Sample Input

3 3 1 2 1 3 2 3

Sample Output

1 3 1 3 -2

Source

​​2018 Multi-University Training Contest 2 ​​

Recommend

chendu|We have carefully selected several similar problems for you:​​6318​​​​​6317​​​​​6316​​​​​6315​​​​​6314​​

​​Statistic​​​|​​Submit​​​|​​Discuss​​​ | ​​Note​​