hdu6311Cover
题意：有最少用多少条边不重复的路径可以覆盖一个张无向图。
分析：对于一个连通块（单个点除外），如果奇度数点个数为 k，那么至少需要max{k/2,1} 条路径。将奇度数的点两两相连边（虚边），然后先从奇度数的点出发，搜索由其出发的欧拉回路。需要将遍历的边和其反向边打标记，并在DFS退栈的时候记录边的编号（前向星的存储是访问后加入的边），若该边是自己添加的虚边，那么说明实际上这次DFS搜索到的是一条欧拉通路，那么结果还需额外+1，所以对所有奇数点DFS过后，得到的结果就是max{k/2,1}。
再从未被访问过的偶数顶点出发搜索由其出发的欧拉回路，每一次DFS就是找到了一条回路。
代码：
#include <bits/stdc++.h> #define INF 0x3f3f3f3f #define LL long long #define mem(i,j) memset(i,j,sizeof(i)) using namespace std; const int N=1e5+5; int n, m; struct EDGE { int to,nt; int id; bool f; }E[N<<4]; int head[N], tot; void addE(int u,int v,int id) { E[tot].f=0; E[tot].to=v; E[tot].id=id; E[tot].nt=head[u]; head[u]=tot++; } bool vis[N]; int deg[N], cnt; vector <int> ans[N]; void init() { tot=cnt=0; mem(head,-1); mem(deg,0); mem(vis,0); } void dfs(int u) { vis[u]=1; for(int i=head[u];~i;i=E[i].nt) { int v=E[i].to, id=E[i].id; if(!E[i].f) { E[i].f=E[i^1].f=1; // 这条边和对应的反向边标记 dfs(v); // 一直搜到终点 if(id) ans[cnt].push_back(-id); // 从终点开始反向记录路径 所以是-id else cnt++; // id为0说明遇到了手动加的边 就是新的一笔 } } } int main() { while(~scanf("%d%d",&n,&m)) { init(); for(int i=1;i<=m;i++) { int u,v; scanf("%d%d",&u,&v); deg[u]++, deg[v]++; addE(u,v,i); addE(v,u,-i); } int u=0; for(int i=1;i<=n;i++) if(deg[i]&1) { // 奇数度的点 两两连边 if(u) addE(u,i,0), addE(i,u,0), u=0; else u=i; } for(int i=1;i<=n;i++) if(!vis[i] && (deg[i]&1)) { /// 先从奇数点开始搜 cnt++; dfs(i); cnt--; // cnt记录的是之前的最后一条路 } // 所以记录新的路应该cnt++先移到下一条路 // 搜索过程中一直cnt++所以搜索结束后cnt是在下一条路 // 此时将cnt置为最后一条路 应该cnt-- for(int i=1;i<=n;i++) if(!vis[i] && deg[i]) { cnt++; dfs(i); } // 此时还未走过的点都是偶数点 形成一个环 所以不需要cnt-- printf("%d ",cnt); for(int i=1;i<=cnt;i++) { int len=ans[i].size(); printf("%d",len); for(int j=0;j<len;j++) printf(" %d",ans[i][j]); printf(" "); ans[i].clear(); } } return 0; }