首页 > Telephone Lines
开通博客写题解
头像 Dear㉿You
发表于 2020-09-11 15:47:35
题意 求1到n的所有路中的最小的第k+1长的路。 分析 题目中说，可指定免费修k条路，而最终的费用就取决于边权值第k+1大的边。所以可以二分其值，每次二分出一个mid，跑spfa，求出到n最少要免费牵多少根线。如果小于等于k条，说明这条边还可以更小。 代码 #include<ios 展开全文
去ta的博客 赞 (6) 回复(0) 收起
头像 __故人__
发表于 2020-09-12 10:39:15
分析 因为有 条可以免费，所以我们朴素的最短路算法不太好做。现在题解中有了二分最短路的题解。这里换一种思路。分层图。每一层和原图是相同的，层与层之间由边权为 的边链接。最后一层的终点的权值就是我们要求的最小值。 代码 #include<bits/stdc++.h> using nam 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 又在摸鱼的大熊猫很勤奋努力
发表于 2020-09-12 16:19:47
Telephone Line S 题目大意: 首先你有一张图，问你从到的路径中第条最大的边最小有多大 分析： 这个题很显然是可以二分答案的但是我们考虑换一种做法：分层图那么就是跨层的时候让其代价为，那么一共就有层图在跑一个类似最短路的东西就可以了 #include <bits/stdc++.h 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 DeNeRATe
发表于 2020-09-12 18:33:08
分析 本题主要就是一个转化当我们看到数据范围，就可以大胆猜测较高复杂度的算法因为维护最大值比较麻烦我们考虑用二分答案限制最大值然后就可以顺理成章的想出将的路径长度标为1跑一个最短路如果最后的Dist[T]那么这就是一个可行的解以此二分即可求得答案 代码 //P1948 #include <io 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 熠丶
发表于 2020-09-12 19:01:32
题意：求原点1到n的所有路中的第k+1长的路最小 做法：邻接表优化的dijkstra+二分 思路： 1.先找到二分所需要的边界条件l,r2.对于长度小于二分出的答案的线段，因为不需要付价钱，所以可以将其权值看作是0;同理，大于二分的值的路径，我们将长度看作1(意味着我需要使用1次免费的资格)3.跑d 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 Jason237
发表于 2019-08-21 08:23:45
题面描述： 在某地有n座通信基站，p条双向电缆，第i条连接ai和bi。其中1号基站是总站，现有人希望通讯公司可以对电缆进行升级以期更好地使用，其中对第i条升级需要支付wi。 而电缆公司正在搞活动，某人可以指定一条从1号基站到n号基站的路径，并指定路径上不超过k条电缆，通讯公司可免费进行升级，而收取的 展开全文
去ta的博客 赞 (1) 回复(1) 收起
头像 嘻嘻嘻嘻嘻嘻嘻
发表于 2020-09-13 17:00:51
题：https://ac.nowcoder.com/acm/problem/24950题意：给n点，m边无向图，dis[u,v]代表从u到v的路径上边的最大值，现在给定整数k，代表可以抵消掉k条边，问dis[1,n]的最小值。分析：n<=1000,不能直接地对原图进行最短路，我们可以考虑二分考 展开全文
去ta的博客 赞 (1) 回复(1) 收起
头像 savage
发表于 2019-08-15 15:38:15
题目描述 Farmer John wants to set up a telephone line at his farm. Unfortunately, the phone company is uncooperative, so he needs to pay for some of 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”