CCF 送货

我会带着你远行 2021-09-14 03:06 434阅读 0赞

## **一、试题** ##

问题描述  
　　为了增加公司收入，F公司新开设了物流业务。由于F公司在业界的良好口碑，物流业务一开通即受到了消费者的欢迎，物流业务马上遍及了城市的每条街道。然而，F公司现在只安排了小明一个人负责所有街道的服务。  
　　任务虽然繁重，但是小明有足够的信心，他拿到了城市的地图，准备研究最好的方案。城市中有n个交叉路口，m条街道连接在这些交叉路口之间，每条街道的首尾都正好连接着一个交叉路口。除开街道的首尾端点，街道不会在其他位置与其他街道相交。每个交叉路口都至少连接着一条街道，有的交叉路口可能只连接着一条或两条街道。  
　　小明希望设计一个方案，从编号为1的交叉路口出发，每次必须沿街道去往街道另一端的路口，再从新的路口出发去往下一个路口，直到所有的街道都经过了正好一次。  
输入格式  
　　输入的第一行包含两个整数n, m，表示交叉路口的数量和街道的数量，交叉路口从1到n标号。  
　　接下来m行，每行两个整数a, b，表示和标号为a的交叉路口和标号为b的交叉路口之间有一条街道，街道是双向的，小明可以从任意一端走向另一端。两个路口之间最多有一条街道。  
输出格式  
　　如果小明可以经过每条街道正好一次，则输出一行包含m+1个整数p1, p2, p3, …, pm+1，表示小明经过的路口的顺序，相邻两个整数之间用一个空格分隔。如果有多种方案满足条件，则输出字典序最小的一种方案，即首先保证p1最小，p1最小的前提下再保证p2最小，依此类推。  
　　如果不存在方案使得小明经过每条街道正好一次，则输出一个整数-1。  
样例输入  
4 5  
1 2  
1 3  
1 4  
2 4  
3 4  
样例输出  
1 2 4 1 3 4  
样例说明  
　　城市的地图和小明的路径如下图所示。

样例输入  
4 6  
1 2  
1 3  
1 4  
2 4  
3 4  
2 3  
样例输出  
\-1  
样例说明  
　　城市的地图如下图所示，不存在满足条件的路径。

评测用例规模与约定  
　　前30%的评测用例满足：1 ≤ n ≤ 10, n-1 ≤ m ≤ 20。  
　　前50%的评测用例满足：1 ≤ n ≤ 100, n-1 ≤ m ≤ 10000。  
　　所有评测用例满足：1 ≤ n ≤ 10000，n-1 ≤ m ≤ 100000。

## **二、代码** ##

在不了解[欧拉通路][Link 1]情况下，首先想到纯深度搜索，只要搜得到就行。结果只有50分，看代码不知道错在哪，哪位仁兄帮忙提点一下。  
50分

#include<iostream>
    #include<vector>
    #include<algorithm>
    
    using namespace std;
    
    #define NMAX 10050
    
    int n,m;
    int s,e;
    vector<int> road[NMAX];
    bool visit[NMAX][NMAX];
    vector<int> out;
    
    bool DFS(int from){
        // 整个深度搜索思想很简单：我选一条路线进行搜索，如果到底后我们out记录数达到路径数量，说明找到路线，因为out不可能重复记录路线。
    
        int length = road[from].size();
        for(int i=0; i<length; i++){
            int to = road[from][i];
    
            if(!visit[from][to]){
                // 在搜索时，我们先假设to节点能够找到路径，所以先假设push进out，
                // 当我们到底发现没有找到时，我们再退一步，把from到to的路径访问撤销，out中最后一个to删除。
                visit[from][to] = visit[to][from] = true;
                out.push_back(to);
                bool flag = DFS(to);
                if(!flag){
                    visit[from][to] = visit[to][from] = false;
                    out.erase(out.end()-1);
                }else{
                    return flag;
                }
            }
    
        }
    
        // 递归终结条件：在遍历完from所有出路后，检查是否所有路线都被走过，如果没有返回false
    // if(out.size()==m+1){ 
    // return true;
    // }else{ 
    // return false;
    // }
        return (int)out.size()==m+1?true:false;
    
    }
    
    int main(){
        cin>>n>>m;
        // 邻接表方便取值遍历
        for(int i=0; i<m; i++){
            cin>>s>>e;
            road[s].push_back(e);
            road[e].push_back(s);
        }
        // 对每个节点的出度进行升序排列，在深度搜索时优先选择小的节点,满足题目的字典排序
        for(int i=1; i<=n; i++){
            sort(road[i].begin(),road[i].end());
        }
        out.push_back(1);
        if(DFS(1)){
            for(int j=0; j<(int)out.size(); j++){
                cout<<out[j]<<" ";
            }
        }else{
            cout<< -1;
        }
        return 0;
    
    }

二次更新，但还是50分。了解欧拉通路后，我觉得要考虑某两点为奇出度情况。好多人都认为题中字典序要求是必须从1号起点开始，我的理解为，在所有路径排列中字典序输出最小路径。也就是说有两条路径2,3,4,1,2和3,4,1,2,3我觉得按[字典序][Link 2]首先比较第一个2<3，那么输出2,3,4,1,2。对于欧拉回路，显然从2开始就行，对于二奇点欧拉通路，那应该从较小点出发。

#include<iostream>
    #include<vector>
    #include<algorithm>
    #include<queue>
    
    using namespace std;
    
    #define NMAX 10050
    
    int n,m;
    int s,e;
    vector<int> road[NMAX];
    bool visit[NMAX][NMAX];
    vector<int> out;
    int num,sss=NMAX,start=1;
    //priority_queue<int, vector<int>, greater<int> > pq;
    
    bool DFS(int from){
        // 整个深度搜索思想很简单：我选一条路线进行搜索，如果到底后我们out记录数达到路径数量，说明找到路线，因为out不可能重复记录路线。
    
        int length = road[from].size();
        for(int i=0; i<length; i++){
            int to = road[from][i];
    
            if(!visit[from][to]){
                // 在搜索时，我们先假设to节点能够找到路径，所以先假设push进out，
                // 当我们到底发现没有找到时，我们再退一步，把from到to的路径访问撤销，out中最后一个to删除。
                visit[from][to] = visit[to][from] = true;
                out.push_back(to);
                bool flag = DFS(to);
                if(!flag){
                    visit[from][to] = visit[to][from] = false;
                    out.erase(out.end()-1);
                }else{
                    return flag;
                }
            }
    
        }
    
        // 递归终结条件：在遍历完from所有出路后，检查是否所有路线都被走过，如果没有返回false
    // if(out.size()==m+1){ 
    // return true;
    // }else{ 
    // return false;
    // }
        return (int)out.size()==m+1?true:false;
    
    }
    
    int main(){
        cin>>n>>m;
        // 邻接表方便取值遍历
        for(int i=0; i<m; i++){
            cin>>s>>e;
            road[s].push_back(e);
            road[e].push_back(s);
        }
        // 对每个节点的出度进行升序排列，在深度搜索时优先选择小的节点,满足题目的字典排序
    // pq.push(1);
        for(int i=1; i<=n; i++){
            if(road[i].size()%2==1){
    // pq.push(i);
                  num++;
                  // 取奇度最小点
                  sss = min(i,sss);
            }
            sort(road[i].begin(),road[i].end());
        }
    
        if(num==2){
            start = sss;
        }
    // cout<<start<<endl;
        out.push_back(start);
        if(DFS(start)){
            for(int j=0; j<(int)out.size(); j++){
                cout<<out[j]<<" ";
            }
        }else{
            cout<< -1;
        }
    // if(!pq.empty()){ 
    // int s = pq.top();
    // out.push_back(s);
    // if(DFS(s)){ 
    // for(int j=0; j<(int)out.size(); j++){ 
    // cout<<out[j]<<" ";
    // }
    // }else{ 
    // cout<< -1;
    // }
    // }
    
        return 0;
    
    }

有个其他人80分代码。

#include<bits/stdc++.h>
    using namespace std;
    #define pi pair<int,int>
    #define fi first
    #define se second
    const int maxn=1e5+10;
    int vis1[maxn];
    int path[(int)2e6+10],cc;
    int n,m;int vis[(int)2e6+10],degree[maxn];
    vector<pi>a[maxn];
    map<pi,int>mm;int kk;
    struct node{
        int u,v,id;
    }b[(int)1e6+10];
    void dfs1(int u){
        for(int i=0;i<a[u].size();i++){
            int v=a[u][i].fi;
            if(vis1[v]) continue;
            vis1[v]=1;
            dfs1(v);
        }
    }
    int flag;
    void dfs2(int u){
        //path[kk]=u;
        for(int i=0;i<a[u].size();i++){
            int v=a[u][i].fi;
            if(vis[a[u][i].se]) continue;
            vis[a[u][i].se]=1;vis[a[u][i].se^1]=1;
            dfs2(v);
            path[kk++]=v;
        }
    }
    bool cmp(node a,node b){
        if(a.u==b.u)return a.v<b.v;
        return a.u<b.u;
    }
    int main(){
        scanf("%d%d",&n,&m);cc=1;int u,v; kk=2;flag=0;
        for(int i=1;i<=2*m-1;i+=2){
            scanf("%d%d",&b[i].u,&b[i].v);
        // a[u].push_back({v,kk++});a[v].push_back({u,kk++});
            degree[b[i].u]++;degree[b[i].v]++;b[i].id=i-1;
            b[i+1].u=b[i].v;b[i+1].v=b[i].u;b[i+1].id=i;
        }
        sort(b+1,b+1+2*m,cmp);
        for(int i=1;i<=2*m;i++){
            int u=b[i].u;int v=b[i].v;int num=b[i].id;
        // cout<<" u = "<<u<<" v= "<<v<<"i d = "<<num<<endl;
            a[u].push_back({v,num});
        }
        vis1[1]=1;
        dfs1(1);
        for(int i=1;i<=n;i++){
            if(!vis1[i]){
                puts("-1");return 0;
            }
        }
        int sum=0;
        for(int i=1;i<=n;i++){
            if(degree[i]&1){
                if(cc==1){
                    path[cc++]=i;
                }
                sum++;
            }
        }
        if(sum!=0&&sum!=2){
            puts("-1");return 0;
        }
        if(cc==1){
            path[cc++]=1;
        }
        dfs2(path[1]);
        printf("%d ",path[1]);
        for(int i=m+1;i>2;i--){
            printf("%d ",path[i]);
        }
        printf("%d\n",path[2]);
        return 0;
    }

[Link 1]: http://blog.csdn.net/qq_16234613/article/details/77531842
[Link 2]: http://blog.csdn.net/qq_16234613/article/details/77169300