201512-4 ccf 送货 (欧拉路径+神奇的最小字典序）

た入场券 2022-05-14 05:57 172阅读 0赞

题目链接：  
[送货][Link 1]

题目大意：  
中文题，不解释  
不过感觉这题ccf上的测试有问题，好多代码都是80分，然后RE了！！  
出题越来越有水平了啊！！弱鸡瑟瑟发抖

解题思路：  
当然要先判断图是否存在欧拉路径了。  
对于无向图，判断是否存在欧拉路径，首先肯定图要是连通图，其次每个点的数必须为偶数或者恰好有两个点的度数为奇数（就是起始点和终点）。

然后如果题目没有要求最小字典序路径的话，直接用fleury算法求解即可

因为题目要求路径最小字典序，感觉好难，于是看各路神仙写法，先按边u+v的大小排序，然后dfs,把无路可走的点加入答案序列，最后反序输出，就是最小字典序。  
想想好像是这样，但是不好怎么证明，姑且先这样理解。  
至于后面20分RE，我也不知道了，反正没有除0，也没有数组越界，就很迷

AC（80分）代码（本地AC就是AC，傲娇.jpg)：

#include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <vector>
    #include <stack>
    #include <set>
    
    
    using namespace std;
    
    const int MAXN = 1e5;
    int n,m,cnt,top;
    int head[MAXN*2],du[MAXN],vis[MAXN],pre[MAXN],visited[MAXN*2];
    stack<int> sta;
    
    struct P{
        int u,v;
        int sum;
    }p[MAXN*2];
    
    struct node{
        int v;
        int next;
    }g[MAXN*2];
    
    void addedge(int u, int v){
        g[++cnt].v = v; g[cnt].next = head[u];
        head[u] = cnt;
        g[++cnt].v = u; g[cnt].next = head[v];
        head[v] = cnt;
    }
    
    void dfs1(int u){
        vis[u] = 1;
        for(int i=head[u]; i!=-1; i=g[i].next){
            if(!vis[g[i].v]) dfs1(g[i].v);
        }
    }
    
    void dfs(int u){
    
        for(int i=head[u]; i!=-1; i=g[i].next){
            if(visited[i]) continue;
            visited[i] = visited[i^1] = 1;
            dfs(g[i].v);
        }
        pre[++top] = u;
        return ;
    }
    
    
    
    void init(){
        memset(head, -1, sizeof(head));
        memset(vis, 0, sizeof(vis));
        memset(du, 0 ,sizeof(vis));
        memset(visited, 0, sizeof(visited));
        for(int i=0; i<MAXN*2; ++i){
            g[i].next = -1;
        }
        top = 0;
        cnt = -1;
    }
    
    bool cmp(P a, P b){
        return a.sum > b.sum;
    }
    int main(){
        init();
        cin>>n>>m;
        for(int i=0; i<m; ++i){
            int a,b;
            scanf("%d%d",&a,&b);
            p[i].u = a; p[i].v = b;
            p[i].sum = a+b;
            du[a]++; du[b]++;
        }
    
        sort(p,p+m,cmp);
        for(int i=0; i<m; ++i){
            addedge(p[i].u, p[i].v);
        }
    
        dfs1(1);
        int num = 0, flag = 0;
        for(int i=1; i<=n; ++i){
            if(du[i]%2!=0){
                num++;
            }
            if(!vis[i]){
                flag=1;
                break;
            }
        }
    
        if(!flag&&(num==0 || (num==2&&du[1]%2!=0))){
            dfs(1);
            for(int i=top; i>=1; --i){
                if(i>1) cout<<pre[i]<<" ";
                else cout<<pre[i]<<endl;
            }
        }
        else cout<<"-1"<<endl;
        return 0;
    }

[Link 1]: http://118.190.20.162/view.page?gpid=T34