HDU 6311 最少路径覆盖边集欧拉路径

Cover

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1543 Accepted Submission(s): 321
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.

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

3 1 3 -2

Source

2018 Multi-University Training Contest 2

解析对于每个连通块最少路径覆盖就是 max(1,度数为奇数点的个数/2) 然后我们把每两个奇数点连一条虚边要剩两个我们求欧拉路径或者欧拉回路都可以求解求得的路径删掉虚边剩下的线段就是最少的路径但是求欧拉路径比较容易计算路径条数所以剩两个从一个奇数点出发回到另一个奇数点（没有奇数点就从任意一点出发得到欧拉回路没有虚边一条路就可以走完）独立点不要算进来覆盖所有的边不是所有的点。

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

欧拉回路或者欧拉路径都可以直接dfs得到回朔的时候保存路径就好了因为走死一个圈退回去转一圈还可以回来

欧拉回路求解算法：

https://blog.csdn.net/u011466175/article/details/18861415

AC代码

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef long long ll;
  4 const int maxn=1e5+20,mod=1e9+7;
  5 const ll inf=1e16;
  6 #define pb push_back
  7 #define mp make_pair
  8 struct edge
  9 {
 10     int from,to;
 11     edge(int u,int v):from(u),to(v) {}
 12 };
 13 int n,m,cnt;
 14 vector<int> ans[maxn],ji;
 15 vector<edge> edges;
 16 vector<int> g[maxn];
 17 int du[maxn];
 18 int p[maxn*10],vis[maxn];//p标记边是否用过要开大一点 因为自己还要加边，vis标记点是否访问过
 19 void init()
 20 {
 21     cnt=0;
 22     for(int i=0; i<=n; i++) g[i].clear(),ans[i].clear();
 23     memset(vis,0,sizeof(vis));
 24     memset(du,0,sizeof(du));
 25     memset(p,0,sizeof(p));
 26     edges.clear();
 27 }
 28 void addedge(int from,int to)
 29 {
 30     edges.push_back(edge(from,to));
 31     edges.push_back(edge(to,from));
 32     int siz=edges.size();
 33     g[from].push_back(siz-2);
 34     g[to].push_back(siz-1);
 35 }
 36 void dfs(int x)
 37 {
 38     vis[x]=1;
 39     if(du[x]%2)
 40         ji.pb(x);
 41     for(int i=0;i<g[x].size();i++)
 42     {
 43         edge e=edges[g[x][i]];
 44         if(!vis[e.to])
 45             dfs(e.to);
 46     }
 47 }
 48 void dfs2(int x)
 49 {
 50     for(int i=0;i<g[x].size();i++)
 51     {
 52         int u=g[x][i];
 53         edge e=edges[u];
 54         if(!p[u])
 55         {
 56             p[u]=p[u^1]=1;
 57             dfs2(e.to);
 58             int temp=u%2?-u/2-1:u/2+1;
 59             if(u<2*m)
 60                 ans[cnt].pb(temp);
 61             else
 62                 cnt++;
 63         }
 64     }
 65 }
 66 int main()
 67 {
 68     while(~scanf("%d%d",&n,&m))
 69     {
 70         int u,v;init();
 71         for(int i=1;i<=m;i++)
 72         {
 73             scanf("%d%d",&u,&v);
 74             addedge(u,v);
 75             du[u]++,du[v]++;
 76         }
 77         for(int i=1;i<=n;i++)
 78         {
 79             if(!vis[i]&&du[i])
 80             {
 81                 ji.clear();
 82                 dfs(i);
 83                 for(int i=2;i<ji.size();i+=2)
 84                 {
 85                     addedge(ji[i],ji[i+1]);
 86                 }
 87                 int t=ji.size()?ji[0]:i;
 88                 dfs2(t);
 89                 cnt++;
 90             }
 91         }
 92         printf("%d
",cnt);
 93         for(int i=0;i<cnt;i++)
 94         {
 95             printf("%d",ans[i].size());
 96             for(int j=ans[i].size()-1;j>=0;j--)
 97             {
 98                 printf(" %d",ans[i][j]);
 99             }
100             printf("
");
101         }
102     }
103 }

HDU 6311 最少路径覆盖边集 欧拉路径

Cover

HDU 6311 最少路径覆盖边集欧拉路径