2018HDU多校第二场——1003 Cover

你的名字 2022-05-18 01:39 156阅读 0赞

题目链接：[hdu6311][]

题目大意：开始读题时，想到了多少次dfs可以遍历完所有边，就是答案。却没有想到利用添加虚边，进行欧拉路的一个查找，然后再把添加的虚边去掉，剩下的几段搜索路径，就是答案！

简而言之就是给你一个n个点，m条边的无向图，图不一定联通，问你最少需要画几笔才能将这些边都覆盖，同时要输出边的路径方案。

举个例子（来自大佬视频题解的例子）：  
如下一个图，最少需要2笔才可能画（遍历）完所有的边  
那如何把这样的一个问题转换成我们熟悉的套路呢，如果每次dfs一次，把本次遍历的边去掉，然后继续dfs,复杂度比较高，同时也不太好实现  
![这里写图片描述][70]

所以我们考虑将这个图转换成一个欧拉图（也就是图中只有两个度数为奇数的点，或者所有点的度数均为偶数），这样我们只要选择一个度数为奇数的点作为起点跑一遍欧拉回路同时记录路径即可（如果所有点的度数都是偶数的话就选任意一个点就行了）

所以看下图：（蓝色为添加的虚边，红色为欧拉路径，右边是dfs的路径）：  
![这里写图片描述][70 1]

这样我们dfs求完欧拉路径，然后遇到虚边，num++,放入另外的一个队列中（相当于上图右边切断虚边，变成了两段，最后输出所有路径方案

遇到的坑：一直TLE，原来是边的数组开太小了，没有考虑要加虚边进去，可是奇怪为啥HUD不给RW，一直TLE，查了好久23333333.。。。！！！  
AC代码如下（参考了标程，感觉掌握进制运算的一些技巧好厉害啊，比如&  
1去判断奇数，^1得到相邻的两个下标，膜大佬）：

#include <bits/stdc++.h>
    
    using namespace std;
    
    const int MAXN = 100007;
    
    int n,m;
    struct edge{
        int v;
        int next;
    }E[MAXN<<2];
    
    int first[MAXN],du[MAXN],vis[MAXN],visE[MAXN<<2];
    int cnt,num;
    vector<int> temp,ans[MAXN];
    void init(){
        memset(first, -1, sizeof(first));
        memset(du, 0, sizeof(du));
        memset(vis, 0, sizeof(vis));
        memset(visE, 0, sizeof(visE));
        num = 0;
        cnt = 1;
        temp.clear(); 
    }
    
    void addedge(int u,int v){
        E[++cnt].v =v;
        E[cnt].next =first[u];
        first[u] =cnt;
    }
    
    void dfs(int u){
        vis[u]=1;
        if(du[u]&1) temp.push_back(u); //如果度数为奇数，则加入进去 
        for(int i=first[u]; i!=-1; i=E[i].next){
            int v=E[i].v;
            if(!vis[v]) dfs(v);
        }
    }
    
    void dfs2(int u){
        for(int i=first[u]; i!=-1; i=E[i].next){
            if(!visE[i]){
                visE[i]=visE[i^1]=1;
                int v=E[i].v;
                dfs2(v);
                if(i>2*m+1) num++;
                else{
                    int ret=i&1?(i/2):(-i/2); //判断和输入方向是否一致 
                    ans[num].push_back(ret);
                }
            }
        }
    }
    void solve(){
        for(int i=1; i<=n; ++i){
            if(!vis[i]&&du[i]){
                dfs(i);
                int sz=temp.size();
                for(int j=2; j<sz; j+=2){  //保留两个度数为奇数的点 
                    addedge(temp[j],temp[j+1]);
                    addedge(temp[j+1],temp[j]);
                }
                num++;
                if(temp.size()) dfs2(temp[0]);
                else dfs2(i);
                temp.clear();
            }
        }
    
    }
    
    void output(){
        printf("%d\n",num);
        for(int i=1; i<=num; ++i){
            int l=ans[i].size();
            printf("%d ",l);
            for(int j=0; j<l-1; ++j){
                printf("%d ",ans[i][j]);
            }
            printf("%d\n",ans[i][l-1]);
            ans[i].clear();
        }
    } 
    
    int main(){
        while(~scanf("%d%d",&n,&m)){
            init(); 
            int x,y;
            for(int i=1; i<=m; ++i){
                scanf("%d%d",&x,&y);
                addedge(x,y);
                addedge(y,x);
                du[x]++; du[y]++; //度数加一 
            }
            solve();
            output(); 
        }
        return 0;
    }

[hdu6311]: http://acm.hdu.edu.cn/showproblem.php?pid=6311
[70]: /images/20220518/be52753db1ae4e888df2cb9c2c9481c4.png
[70 1]: /images/20220518/aa5b78d096a6434eb8766fa5848ac6d1.png