本文共 2144 字，大约阅读时间需要 7 分钟。

电话网络

时间限制: 1 Sec 内存限制: 128 MB 题目描述 由于地震使得连接汶川县城电话线全部损坏，假如你是负责将电话线接到震中汶川县城的负责人，汶川县城周围分布着N(1≤N≤1,000)根按 1…N 顺次编号的废弃的电话线杆，任意两根电话线杆间都没有电话线相连。一共P(1≤P≤10,000)对电话线杆间可以拉电话线，其余的由于地震使得无法被连接。 第i对电话线杆的两个端点分别为Ai，Bi，它们间的距离为Li(1≤Li≤1,000,000)。数据中保证每对(Ai，Bi)最多只出现1次。编号为1的电话线杆已经接人了全国的电话网络，整个县城的电话线全都连到了编号为N的电话线杆上。也就是说，你的任务仅仅是找一条 将1号和N号电话线杆连起来的路径，其余的电话线杆并不一定要连人电话网络。电信公司决定支援灾区免费为汶川县城连结K(0≤K<N)对由你指定的电话线杆。对于此外的那些电话线，需要为它们付费，总费用等于其中最长的电话线的长度(每根电话线仅连接一对电话线杆)。如果需要连接的电话线杆不超过K对，那么总支出为0。 请你计算一下，将电话线引到震中汶川县城最少需要在电话线上花多少钱? 输入 第一行包含三个用空格隔开的整数：N，P和K。 第二行到第P+1行：每行分别都为空格隔开的整数：Ai，Bi和Li。 输出 仅包含一个整数，表示在这项工程上的最小支出。如果任务不可能完成，则输出-1。 样例输入 Copy 5 7 1 1 2 5 3 1 4 2 4 8 3 2 3 5 2 9 3 4 7 4 5 6 样例输出 Copy 4

求最大值最小，本能的想到可以用二分来做。

显然这个题是要二分 花费的钱 ，主要在于怎么写check函数。对于一个mid，做一遍最短路，但是这里最短路加的不是每个边的边权，而是0和1，因为二分选出来的mid是去除k条大边后，剩余边的最大值，所以当这个边大于mid的时候，就说明需要用支援的免费电话线杆，此时 dis + 1，而小于等于 mid 的时候，可以直接付款，此时 dis + 0 ，从1到n做一遍最短路，看dis[n]是否<=k即可。 还要处理一下无解的情况，无解的时候应该是1和n不连通的时候，根据二分模板的不同，处理的方法可能不一样，说一下我的吧。由于不连通，check函数始终返回false，那么一直会执行 l = mid + 1 ，一直到最后 l = r 此时的 r 仍为 1e10，所以 l = 1e10 的时候直接输出 -1 即可。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
      
     
    
   

转载地址：https://blog.csdn.net/DaNIelLAk/article/details/105668905 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！