专栏首页AI那点小事CCF考试——201703-3地铁修建

CCF考试——201703-3地铁修建

概要

问题描述

  A市有n个交通枢纽,其中1号和n号非常重要,为了加强运输能力,A市决定在1号到n号枢纽间修建一条地铁。   地铁由很多段隧道组成,每段隧道连接两个交通枢纽。经过勘探,有m段隧道作为候选,两个交通枢纽之间最多只有一条候选的隧道,没有隧道两端连接着同一个交通枢纽。   现在有n家隧道施工的公司,每段候选的隧道只能由一个公司施工,每家公司施工需要的天数一致。而每家公司最多只能修建一条候选隧道。所有公司同时开始施工。   作为项目负责人,你获得了候选隧道的信息,现在你可以按自己的想法选择一部分隧道进行施工,请问修建整条地铁最少需要多少天。

输入格式

  输入的第一行包含两个整数n, m,用一个空格分隔,分别表示交通枢纽的数量和候选隧道的数量。   第2行到第m+1行,每行包含三个整数a, b, c,表示枢纽a和枢纽b之间可以修建一条隧道,需要的时间为c天。

输出格式

  输出一个整数,修建整条地铁线路最少需要的天数。

样例输入

6 6 1 2 4 2 3 4 3 6 7 1 4 2 4 5 5 5 6 6

样例输出

6

样例说明

  可以修建的线路有两种。   第一种经过的枢纽依次为1, 2, 3, 6,所需要的时间分别是4, 4, 7,则整条地铁线需要7天修完;   第二种经过的枢纽依次为1, 4, 5, 6,所需要的时间分别是2, 5, 6,则整条地铁线需要6天修完。   第二种方案所用的天数更少。

评测用例规模与约定

  对于20%的评测用例,1 ≤ n ≤ 10,1 ≤ m ≤ 20;   对于40%的评测用例,1 ≤ n ≤ 100,1 ≤ m ≤ 1000;   对于60%的评测用例,1 ≤ n ≤ 1000,1 ≤ m ≤ 10000,1 ≤ c ≤ 1000;   对于80%的评测用例,1 ≤ n ≤ 10000,1 ≤ m ≤ 100000;   对于100%的评测用例,1 ≤ n ≤ 100000,1 ≤ m ≤ 200000,1 ≤ a, b ≤ n,1 ≤ c ≤ 1000000。

  所有评测用例保证在所有候选隧道都修通时1号枢纽可以通过隧道到达其他所有枢纽。


思路

咋一看像是图论问题,仔细一琢磨是并查集的应用,题意就是要判断1号结点到N结点之间是否连通,且耗时最短。方法是把所有边导入最小堆里,堆不为空时,一次删除边,最短耗时为该边所修时间,并把边的2端结点连通,若1与N连通则跳出循环。


AC代码

#include <iostream>
#include <queue> 
#include <cstring>
using namespace std;

typedef struct node{
    long long start;
    long long end;
    long long day;
    node(long long s,long long e,long long d){
        start = s;
        end = e;
        day = d;
    }
}Edge;

struct cmp{
    bool operator() (Edge e1,Edge e2){
        return e1.day>e2.day;
    }
};

priority_queue<Edge,vector<Edge>,cmp> q;
long long N,M;
long long s,e,d;
long long data[100001];
bool flag;
long long Min = -1000000;

int Find(int root)
{
    if(data[root] < 0){
        return root;
    }else{
        return data[root] = Find(data[root]);
    }
}

void Union(int root1 ,int root2)
{
    root1 = Find(root1);
    root2 = Find(root2);
    if(root1 == root2){
        return;
    }else if(root1 < root2){
        data[root1] += data[root2];
        data[root2] = root1;
    }else{
        data[root2] += data[root1];
        data[root1] = root2;
    } 
}

int main()
{
    cin>>N>>M;
    for(int i = 0 ; i < M ; i++){
        cin>>s>>e>>d;
        q.push(Edge(s,e,d));
    }
    for(int i = 1 ; i <= N ; i++){
        data[i] = -1;
    }
    while(!q.empty()){
        Edge edge = q.top();
        q.pop();
        Union(edge.start,edge.end);
        if(edge.day > Min){
            Min = edge.day; 
        }
        flag = (Find(1) == Find(N))?true:false;
        if(flag){
            break;
        }
    }
    cout<<Min<<endl;

    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • CCF考试——201709-5除法

      小葱喜欢除法,所以他给了你N个数a1, a2, ⋯, aN,并且希望你执行M次操作,每次操作可能有以下两种:   给你三个数l, r, v,你需要将a...

    AI那点小事
  • 开心的金明

    A1156. 开心的金明 时间限制:1.0s 内存限制:256.0MB 总提交次数: AC次数: 平均分: 将本题分享到: 查...

    AI那点小事
  • 历届试题 兰顿蚂蚁

      平面上的正方形格子被填上黑色或白色。在其中一格正方形内有一只“蚂蚁”。   蚂蚁的头部朝向为:上下左右其中一方。

    AI那点小事
  • 安全AI挑战者计划,邀你共同成长为DL时代的「模型黑客」

    随着机器学习模型能力越来越强、效率越来越高,它已经逐步应用到各种实际场景中。但是 AI 模型本身也会面临很多安全问题,最受关注的就是对抗样本,它能欺骗深度模型。...

    机器之心
  • 零拷贝( Zore Copy )

    零拷贝是实现高速数据传输的一种协议。数据从源节点传送到目的节点的过程中不经过中间缓存。

    兜兜毛毛
  • atomicLong源码分析详解

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    suveng
  • AI大势所趋 布局方向决定未来成败| 报告

    T客汇官网:tikehui.com 撰文 | 张珅健 在全球范围内,IT部门目前是对认知技术最普及的部门(受访者中68%),第二名为客户服务部(32%),之后则...

    人称T客
  • #7 Python顺序、条件、循环语句

    上一节讲解了Python的数据类型和运算,本节将继续深入,涉及Python的语句结构,相当于Python的语法,是以后编写程序的重要基础!

    py3study
  • 23种设计模式之原型模式

    通俗的讲,就是不再使用new 来创建对象, 而改用 clone 方法来得到新的对象

    烟草的香味
  • 用了几年的C语言后你总结了哪些C语言的精髓,是否可以说下心得体会?

    作为从事嵌入式软件开发十几年的程序员,来尝试着回答这个问题,嵌入式开发最基本的编程语言当属于C语言了,这门编程语言最大的特点是灵活高效,现在大学开设相关的编程课...

    程序员互动联盟

扫码关注云+社区

领取腾讯云代金券