POJ 3662 Telephone Lines 二分,最小化第k大的数

这篇具有很好参考价值的文章主要介绍了POJ 3662 Telephone Lines 二分,最小化第k大的数。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、题目大意

我们有n个点,p条边,最小化从1到n之间的路径的第k+1大的数(当路径不超过k时就是0)

二、解题思路

我们首先用dijkstra过一遍,判断从1能不能到n,不能直接输出-1结束。

1能到达n的话,就对二分第k+1大的边进行二分,left选-1,right选最大的边的长度+1(这里我left一开始选取的时最小边-1,后来发现当k比较大时结果可能是0)

二分的依据如下文章来源地址https://www.toymoban.com/news/detail-700650.html

设二分的值为mid
记录从1到n的路径中必走的大于mid的值的数量
如果超过了k,那么放大mid
如果小于等于k,那么缩小mid,同时记录

这样不断循环,直到找到一个临界值limit
当mid=limit时,大于mid的边小于等于k个
当mid=limit-1时,大于mid的边超过k个
那么limit一定就是第k+1大的边

输出最后一个(大于mid的边数小于等于k的)mid即可

三、代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
typedef pair<int, int> P;
vector<P> edges[1007];
bool used[1007];
int n, p, k, d[1007], inf = 0x3f3f3f3f, maxt = 0;
void input()
{
    int from, to, cost;
    scanf("%d%d%d", &n, &p, &k);
    for (int i = 0; i < p; i++)
    {
        scanf("%d%d%d", &from, &to, &cost);
        edges[from - 1].push_back(P(cost, to - 1));
        edges[to - 1].push_back(P(cost, from - 1));
        maxt = max(cost, maxt);
    }
}
bool judgeByDijkstra(int mid)
{
    for (int i = 0; i < n; i++)
    {
        d[i] = inf;
        used[i] = false;
    }
    d[0] = 0;
    priority_queue<P, vector<P>, greater<P>> que;
    que.push(P(d[0], 0));
    while (!que.empty())
    {
        P current = que.top();
        que.pop();
        if (used[current.second] || current.first > d[current.second])
        {
            continue;
        }
        used[current.second] = true;
        for (int i = 0; i < edges[current.second].size(); i++)
        {
            P toEdge = edges[current.second][i];
            int relativeEdge = toEdge.first > mid ? 1 : 0;
            if (d[current.second] + relativeEdge < d[toEdge.second])
            {
                d[toEdge.second] = d[current.second] + relativeEdge;
                que.push(P(d[toEdge.second], toEdge.second));
            }
        }
    }
    return d[n - 1] <= k;
}
void binarySearch()
{
    int left = -1, right = maxt + 1;
    while (left + 1 < right)
    {
        int mid = (left + right) / 2;
        if (judgeByDijkstra(mid))
        {
            right = mid;
        }
        else
        {
            left = mid;
        }
    }
    printf("%d\n", right);
}
bool judgeIfCanGet()
{
    for (int i = 0; i < n; i++)
    {
        d[i] = inf;
        used[i] = false;
    }
    d[0] = 0;
    priority_queue<P, vector<P>, greater<P>> que;
    que.push(P(d[0], 0));
    while (!que.empty())
    {
        P current = que.top();
        que.pop();
        if (used[current.second] || current.first > d[current.second])
        {
            continue;
        }
        used[current.second] = true;
        for (int i = 0; i < edges[current.second].size(); i++)
        {
            P toEdge = edges[current.second][i];
            if (d[current.second] + toEdge.first < d[toEdge.second])
            {
                d[toEdge.second] = d[current.second] + toEdge.first;
                que.push(P(d[toEdge.second], toEdge.second));
            }
        }
    }
    return d[n - 1] != inf;
}
int main()
{
    input();
    if (!judgeIfCanGet())
    {
        printf("-1\n");
    }
    else
    {
        binarySearch();
    }
    return 0;
}

到了这里,关于POJ 3662 Telephone Lines 二分,最小化第k大的数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • QT最小化程序到托盘运行

    实现程序关闭时最小化托盘的功能 托盘实现显示主页面和退出的功能 支持扩展,直接引用TrayIcon类即可,对外暴露接口 单例实现,可复用 注:博主所有资源永久免费,若有帮助,请点赞转发是对我莫大的帮助 注:博主本人学习过程的分享,引用他人的文章皆会标注原作者

    2024年02月05日
    浏览(51)
  • Qt实现最小化窗口到托盘图标

    目录 前言: 1.先看效果图 2.大致思路以及实现流程 3.具体代码以及解释 4.总结 使用QT开发桌面软件,将软件最小化至托盘这样的功能的是比较常见的,今天自己实现一下这个功能,并进行记录总结。  主要功能就是当软件开始运行, 在系统托盘会自动出现一个关于本软件的

    2023年04月08日
    浏览(48)
  • LabVIEW开发最小化5G系统测试平台

    LabVIEW开发最小化5G系统测试平台 由于具有大量存储能力和数据的应用程序的智能手机的激增,当前一代产品被迫提高其吞吐效率。正交频分复用由于其卓越的品质,如单抽头均衡和具有成本效益的实施,现在被广泛用作物理层技术。这些好处是以严格的同步、正交性和高功耗

    2024年02月12日
    浏览(41)
  • unity发布设置(最小化、置顶、限制单开)

    1. 勾上下图标红处,发布后可防止按windows键缩小  2.发布后程序默认最小化 3.发布的程序只能开一个进程

    2024年02月12日
    浏览(42)
  • 最小化安装Linux系统初始化脚本

    目录 最小化安装Linux系统初始化脚本 注:此脚本适用于centos 7/8、Ubuntu1804,具体需要根据实际情况进行测试调整。 此脚本包含的功能: 允许 root 用户使用 ssh 登录 关闭 selinux 关闭防火墙 设置 ps1 设置默认编辑器为 vim 自定义 vim 自定义历史命令 修改内核参数 设置资源限制 修

    2024年02月12日
    浏览(44)
  • leetcode 2616. 最小化数对的最大差值

    在数组nums中找到p个数对,使差值绝对值的和最小。 思路: 最小差值应该是数值相近的一对数之间产生,让数值相近的数字尽量靠在一起方便计算,所以需要排序。 这里不去直接考虑一对对的数字,而是直接考虑差值的取值。 用binary search搜索一个差值。 左边界是0,右边界

    2024年02月13日
    浏览(38)
  • 【深度优先搜索】【图论】【树】2646. 最小化旅行的价格总和

    【数位dp】【动态规划】【状态压缩】【推荐】1012. 至少有 1 位重复的数字 深度优先搜索 图论 树 现有一棵无向、无根的树,树中有 n 个节点,按从 0 到 n - 1 编号。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ,其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在

    2024年02月19日
    浏览(40)
  • mac 最小化全部程序回到桌面(基于alfred workflow)

    换到 mac 系统之后,很多快捷键根本就不好用,组合太多了,除了 cmd + Q/W/A/S/X/R/Z/C/V ,个人认为其它的真的一坨屎。像我的需求就是,开的窗口太多了,我需要全部最小化,再重新打开我需要那个窗口。而 Windows 上的 win + D 就是很符合我的需求,于是我研究一下 mac 怎么实现

    2024年04月17日
    浏览(45)
  • 原子范数 Atomic norm最小化: 简单的Matlab例程

    基于 压缩感知的尽头: 原子范数最小化 中的原子范数最小化算法, 笔者做了一些matlab的仿真, 作为简单的例程,希望帮助大家进一步理解算法和自定义的拓展。 由于凸问题的求解需要使用 CVX, 因此需要读者先自行安装好 matlab 的 CVX包。 假设接收天线有 64 64 6 4 根, 有 3

    2023年04月08日
    浏览(94)
  • C# 实现winform软件最小化到系统托盘,开机自启动

      问题描述   用户的电脑是win7系统,应用系统在用户电脑上运行时部分功能需要访问注册表,但是使用这些功能时会提示用户没有权限访问注册表。 原因分析   win7及后续高版本系统对用户的权限控制比较严,就算用户的权限较高,但用户启动程序时默认还是以普通用

    2024年02月03日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包