CSP 201512-4 送货

简介: CSP 201512-4 送货

问题描述

image.png

输入格式

image.png

输出格式

image.png

数据范围

image.png

输入样例1:

4 5
1 2
1 3
1 4
2 4
3 4

输出样例1:

1 2 4 1 3 4

样例1解释

城市的地图和小明的路径如下图所示。

image.png

输入样例2:

4 6
1 2
1 3
1 4
2 4
3 4
2 3

输出样例2:

-1

样例2解释

城市的地图如下图所示,不存在满足条件的路径。

image.png

本题链接:http://118.190.20.162/view.page?gpid=T34

AC代码

C++

#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
const int N = 10010, M = 100010;
int n, m;
set<int> g[N];
int p[N];
int ans[M], top;
int find(int x)      // 并查集
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
void dfs(int u)
{
    while (g[u].size())
    {
        int t = *g[u].begin();
        g[u].erase(t), g[t].erase(u);  // 删边
        dfs(t);
    }
    ans[ ++ top] = u;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) p[i] = i;   // 初始化p数组
    while (m -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        g[a].insert(b), g[b].insert(a);
        p[find(a)] = find(b);
    }
    int s = 0;
    for (int i = 1; i <= n; i ++ )
        if (find(i) != find(1))      // 不是连通图
        {
            puts("-1");
            return 0;
        }
        else if (g[i].size() % 2) s ++ ; // s记录的是度数为奇数的点的
    // 度数为奇数的点不是0个或2个,或者度数为奇数的点为2个但是起点的度数不是奇数,则不符合欧拉路径
    if (s != 0 && s != 2 || s == 2 && g[1].size() % 2 == 0)
    {
        puts("-1");
        return 0;
    }
    dfs(1);    // 开始遍历欧拉路径
    for (int i = top; i; i -- )   // 欧拉路径实际上记录的是倒序,故求正向欧拉路径需要逆序输出
        printf("%d ", ans[i]);
    return 0;
}

java

注:java版代码只有50分

import java.util.*;
public class Main {
    final int N = 100010;
    int n, m;
    int[] ans = new int[N];
    int top;
    int[] p = new int[10010];
    TreeSet[] g = new TreeSet[10010];
    void run() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for (int i = 0; i <= n; i++) {
            g[i] = new TreeSet();
        }
        for (int i = 1; i <= n; i++) {
            p[i] = i;
        }
        while (m -- != 0) {
            int a, b;
            a = sc.nextInt();
            b = sc.nextInt();
            g[a].add(b);
            g[b].add(a);
            p[find(a)] = find(b);
        }
        int s = 0;
        for (int i = 1; i <= n; i++) {
            if (find(i) != find(1)) {
                System.out.println("-1");
                return;
            } else if (g[i].size() % 2 != 0)  {
                s++;
            }
        }
        if (s != 0 && s != 2 || (s == 2 && g[1].size() % 2 == 0)) {
            System.out.println("-1");
            return;
        }
        dfs(1);
        for (int i = top; i != 0; i--) {
            System.out.printf("%d ", ans[i]);
        }
    }
    void dfs(int u) {
        while (g[u].size() != 0) {
            int t = (Integer) g[u].first();
            g[u].remove(t);
            g[t].remove(u);
            dfs(t);
        }
        ans[ ++ top] = u;
    }
    int find(int x) {
        if (p[x] != x) {
            p[x] = find(p[x]);
        }
        return p[x];
    }
    public static void main(String[] args) {
        new Main().run();
    }
}

代码解释

从一个点出发,不重不漏的经过图中每一条边的一条路径(允许多次经过同一个点)。

从一个点出发,不重不漏的经过图中每一条边的一条路径(允许多次经过同一个点)。如果此路径的起点和终点相同,则称其为一条欧拉回路。

入度(indegree)就是有向图中指向这个点的边的数量,即有向图的某个顶点作为终点的次数和

出度(outdegree)就是从这个点出去的边的数量,即有向图的某个顶点作为起点的次数和

一个点的度(degree)指图中与该点相连的边数

无向连通图

欧拉回路:所有点的度数都为偶数即为有欧拉回路

欧拉路径:度数为奇数的点要么有2个要么有0个

若为0个那么从任意点出发都可以,如果有2个,那么起点必须是其中一个点,终点必须为另一个点


有向连通图

欧拉回路:所有点的入度等于出度

欧拉路径:1.所有点的入度等于出度 2.有一个点(终点)的入度=出度+1,且存在一个点(起点)的出度=入度+1


从当前点出发,只要有出去的边就往外走,深度优先遍历,回溯路径就是它的一个方案

为什么从起点搜到终点不是一个方案?

因为在搜索的过程中,不一定会把所有的边全部走到(有一堆额外的环),但因为起点和终点是唯一的,

且其余点的度数均为偶数,故我们在回溯的过程中把其他的结点(那些没有走过的环)补充到搜索图中即可

字典序最小:从当前点出去搜的时候,按照编号从小到大搜索一遍,就可以保证字典序最小


欧拉路径证明(无向图)

对于起点而言,设其度数为n,那么起始往出走需要一条边,其余到达起点的话,就必然是进来一次出去一次,故起点的度数必须是奇数

对于终点而言,设其度数为m,那么最终到达需要一条边,其余到达终点的点,需要再次出去,故终点的度数必须是奇数

对于非起点和非终点的其余点,它们只是作为中间的“桥梁”,故到达这些点后还需要离开,故这些点的度数必须是偶数

如果起点和终点是同一个点,那么对于起点(终点)而言,出去需要一条边,最终到达该点需要一条边,其余时候进来必然还要出去,

故在这种情况下,起点(终点)的度为偶数

综上所述,对于一个无向图的欧拉路径而言,度数为奇数的点要么为2个要么为0个,且为2个的时候,这两个点分别做起点和终点

    dfs(u)   // 求得的序列其实是欧拉路径的倒序序列
    {
        for u的所有边
            dfs()  // 扩展
        seq += u   // 把u加到序列中
    }

欧拉路径dfs和一般图论dfs区别:

一般图论dfs用点来判重,时间复杂度在O(n+m)

欧拉路径是用边来判重,如果用一个bool变量来表示每个边是否被搜过,时间复杂度会很高:

举个例子,对于一个点,假设其有m条自环,那么我们在遍历的过程中搜第一条边,搜完之后又回到该点,

此时第一条边已经被用过了,故我们要跳过这一条边搜第二条边,依次类推,在搜第三条边的时候需要跳过第一条边和第二条边

以此类推,在搜完m条边的时候就会跳m^2次,这样对于1e5的数据量显然就会超时

处理方法:每用一条边不是进行简单的标记,而是直接进行删除,这样就可以降为线性时间复杂度

无向图的删除方法:因为建无向图对于每一条边会建立两次(不同方向),故我们在删除的时候还需要对它的反向边进行一次标记

如何根据一条边找到它的反向边:因为建边的时候是按照(0,1),(2,3)…进行建边,故求反向边可直接根据 i^1 求得

上述代码中并未采取这种建边方式,直接把边放入set中,set自然有序,且易直接删边


目录
相关文章
|
算法 C++ 索引
【算法】——全排列算法讲解
【算法】——全排列算法讲解
1379 0
|
11月前
|
数据安全/隐私保护
阿里云号码百科支持哪些功能?号码百科不同功能收费价格表整理
阿里云号码百科提供号码归属、状态查询、二次号检测、在网时长及运营商/企业/身份证要素核验等服务,支持加密通信与风控分析,按套餐包计费,广泛应用于注册验证、广告归因与安全防控场景。
1386 0
|
10月前
|
存储 弹性计算 并行计算
阿里云8核8G云服务器收费标准、实例规格及选配教程
阿里云8核8G云服务器是典型的均衡型配置,CPU与内存配比为1:1,这种配比能兼顾多任务并行计算和常规业务内存需求,既不会像低配置机型那样局限于轻量场景,也不会像高配置机型那样聚焦重度计算,因此广泛适配中小企业核心业务系统、中型网站部署、开发测试环境等场景。该配置仅在ECS云服务器系列中提供,无对应轻量应用服务器版本,2026年的收费标准会根据实例类型、计费方式、地域选择产生明显差异,优惠活动则聚焦长期购买折扣、续费保障及通用补贴,整体定价和福利均贴合不同用户的实际使用需求,无隐性消费和捆绑条件。
772 14
|
11月前
|
运维 Ubuntu Unix
Linux网络打印故障排除(手把手教你解决常见问题)
教程来源https://www.vps5.cn/本教程详解Linux系统下网络打印的配置与故障排除,涵盖CUPS服务安装、Web界面添加打印机、常见问题解决方法,助你轻松实现Ubuntu等系统下的稳定打印。
|
11月前
|
存储 SQL 人工智能
DeepInsight x ChatBI:个人Agent助手养成计划
本文提出“个人Agent助手养成计划”,将AI助手比作需共同成长的新员工,通过自然语言提问、反问澄清、结果验证与产品操作等步骤,逐步打造懂用户的智能助理。结合AI与传统工具,解决使用中的实际问题,推动ChatBI落地。
DeepInsight x ChatBI:个人Agent助手养成计划
|
12月前
|
监控 安全 Ubuntu
Linux网络SSH监控(手把手教你守护服务器远程连接安全)
本文介绍如何通过SSH监控提升Linux服务器安全,涵盖日志查看、fail2ban工具使用、自动化报告生成及安全配置建议,帮助用户及时发现异常登录、防范暴力破解,实现有效的远程连接防护。
|
人工智能 数据可视化 数据挖掘
一个悄然崛起的国产软件,AiPy已开源
当前AI大模型虽智能飙升,却难落地日常。AiPy另辟蹊径,为LLM接上“手脚”,打通Python执行环境,让其真正自动分析数据、生成图表、完成任务,实现从“思考”到“行动”的闭环,被誉为“中国版Manus”,获1.9k星好评。
|
人工智能
接入通义千问3后,B站618期间商单成交效率提升5倍+
B站引入通义千问Qwen3、Qwen-VL等模型打造智能体InsightAgent,助力商业平台“花火”与“必达”提效。花火AI选人功能实现商单成交效率提升5倍以上,必达平台数据洞察效率提升3倍以上,大幅优化品牌合作流程。
621 1
接入通义千问3后,B站618期间商单成交效率提升5倍+
|
分布式计算 Hadoop 数据挖掘
“Hadoop整不明白,数据分析就白搭?”——教你用Hadoop撸清大数据处理那点事
“Hadoop整不明白,数据分析就白搭?”——教你用Hadoop撸清大数据处理那点事
800 34