BZOJ 1614 [Usaco2007 Jan]Telephone Lines架设电话线 (二分+最短路)

时间:2023-01-10 00:40:32

题意:

给一个2e4带正边权的图,可以免费k个边,一条路径的花费为路径上边权最大值,问你1到n的最小花费

思路:

对于一个x,我们如果将大于等于x的边权全部免费,那么至少需要免费的边的数量就是

“设大于等于x的边权的边长为1,其余为0,起点到终点的最短路”

然后如果这个得到的最短路,也就是我们所需要免费的边数小于等于k的话,就可以满足题意了(check)

思考一下可以发现对于任何条件,都存在某一个p,当x取[p, inf]的任意值时,都是可以满足题意的

于是我们就可以二分x并check了

得到p之后跑一遍最短路上的最大值,就是答案了(我每次check成功后记录了一次pre)

这题要注意不连通时候的情况输出-1

update:今天仔细想了一下,其实二分的就是ans+1,最后只需要输出max(ans-1,0)就是答案

然后二分+最短路也只能用于这种路径上边权最大值为费用的题了

代码:

有点像西安邀请赛的二分最短路啊

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<vector>
#include<map> #define fst first
#define sc second
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a))
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define lc root<<1
#define rc root<<1|1
//#define lowbit(x) ((x)&(-x)) using namespace std; typedef double db;
typedef long double ldb;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PI;
typedef pair<ll,ll> PLL; const db eps = 1e-;
const int mod = 1e9+;
const int maxn = 2e6+;
const int maxm = 2e6+;
const int inf = 0x3f3f3f3f; const db pi = acos(-1.0); int n, m, k;
int dist[maxn];
struct node{
int id, d;
node(){}
node(int a,int b) {id = a; d = b;}
bool operator < (const node & a)const{
if(d == a.d) return id > a.id;
else return d > a.d;
}
};
vector<node>e[maxn];
PI pre[maxn];
PI tpre[maxn];
void dijkstra(int s, int ki){
for(int i = ; i <= n; i++) dist[i] = inf;//往往不够大 dist[s] = ;
priority_queue<node>q;
q.push(node(s, dist[s]));
while(!q.empty()){
node top = q.top();
q.pop();
if(top.d != dist[top.id]) continue;
for(int i = ; i < (int)e[top.id].size(); i++){
node x = e[top.id][i];
int d=;
if(x.d>=ki)d=;
if(dist[x.id] > top.d + d){
pre[x.id]=make_pair(top.id,x.d);
dist[x.id] = top.d + d;
q.push(node(x.id, dist[x.id]));
}
}
}
return;
}
int main(){
scanf("%d %d %d", &n, &m, &k);
int ans = -inf;
int l,r;
for(int i = ; i <= m; i++){
int x ,y,w;
scanf("%d %d %d", &x, &y, &w);
e[x].pb(node(y,w));
e[y].pb(node(x,w));
}
l=;r=+;
while(l<=r){
int mid = (l+r)>>;
dijkstra(,mid);
//printf("--%d %d %d ==%d\n",l,r,mid,dist[n]);
if(dist[n]<=k){
for(int i = ; i <= n; i++){
tpre[i]=pre[i];
}
r=mid-;
ans=mid;
}
else l=mid+;
}
//printf("%d\n",ans);
if(ans==-inf)return printf("-1"),;
int res = ;
for(int i = n; i != ; i = tpre[i].fst){
//printf("--%d %d %d\n",i, pre[i].fst, pre[i].sc);
int x = tpre[i].sc;
if(x>=ans)continue;
res = max(res, x);
}
printf("%d",res);
return ;
}
/*
5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6 4 3 1
1 2 2
1 3 5
2 3 3
*/

BZOJ 1614 [Usaco2007 Jan]Telephone Lines架设电话线 (二分+最短路)的更多相关文章

  1. BZOJ 1614&colon; &lbrack;Usaco2007 Jan&rsqb;Telephone Lines架设电话线

    题目 1614: [Usaco2007 Jan]Telephone Lines架设电话线 Time Limit: 5 Sec  Memory Limit: 64 MB Description Farm ...

  2. BZOJ 1614 &lbrack;Usaco2007 Jan&rsqb;Telephone Lines架设电话线:spfa &plus; 二分【路径中最大边长最小】

    题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1614 题意: 给你一个无向图,n个点,m条边. 你需要找出一条从1到n的路径,使得这条路径 ...

  3. BZOJ——1614&colon; &lbrack;Usaco2007 Jan&rsqb;Telephone Lines架设电话线

    Time Limit: 5 Sec  Memory Limit: 64 MBSubmit: 1930  Solved: 823[Submit][Status][Discuss] Description ...

  4. bzoj 1614&colon; &lbrack;Usaco2007 Jan&rsqb;Telephone Lines架设电话线【二分&plus;spfa】

    二分答案,然后把边权大于二分值的的边赋值为1,其他边赋值为0,然后跑spfa最短路看是否满足小于等于k条边在最短路上 #include<iostream> #include<cstd ...

  5. &lbrack;Usaco2007 Jan&rsqb;Telephone Lines架设电话线(最短路,二分)

    [Usaco2007 Jan]Telephone Lines架设电话线 Description FarmerJohn打算将电话线引到自己的农场,但电信公司并不打算为他提供免费服务.于是,FJ必须为此向 ...

  6. &lbrack;Usaco2007 Jan&rsqb;Telephone Lines架设电话线&lbrack;二分答案&plus;最短路思想&rsqb;

    Description Farmer John打算将电话线引到自己的农场,但电信公司并不打算为他提供免费服务.于是,FJ必须为此向电信公司支付一定的费用. FJ的农场周围分布着N(1 <= N ...

  7. 【bzoj1614】&lbrack;Usaco2007 Jan&rsqb;Telephone Lines架设电话线 二分&plus;SPFA

    题目描述 Farmer John打算将电话线引到自己的农场,但电信公司并不打算为他提供免费服务.于是,FJ必须为此向电信公司支付一定的费用. FJ的农场周围分布着N(1 <= N <= 1 ...

  8. BZOJ1614&colon; &lbrack;Usaco2007 Jan&rsqb;Telephone Lines架设电话线

    1614: [Usaco2007 Jan]Telephone Lines架设电话线 Time Limit: 5 Sec  Memory Limit: 64 MBSubmit: 892  Solved: ...

  9. 【bzoj1614】&lbrack;Usaco2007 Jan&rsqb;Telephone Lines架设电话线

    题目描述 Farmer John打算将电话线引到自己的农场,但电信公司并不打算为他提供免费服务.于是,FJ必须为此向电信公司支付一定的费用.     FJ的农场周围分布着N(1 <= N &lt ...

随机推荐

  1. android官方下拉刷新控件SwipeRefreshLayout的使用

    可能开发安卓的人大多数都用过很多下拉刷新的开源组件,但是今天用了官方v4支持包的SwipeRefreshLayout觉得效果也蛮不错的,特拿出来分享. 简介:SwipeRefreshLayout组件只 ...

  2. iOS之关于开发的那点破事&lpar;一&rpar;

    前言: 前段时间,经理突然找我说:能不能在项目中对缓存的图片进行加密?当时就感到疑惑,就说:可以是可以,但为什么要这样做?有什么意义没? 我们都知道,apple使用的沙盒(sandbox)机制,这种机 ...

  3. RDD中cache和persist的区别

    通过观察RDD.scala源代码即可知道cache和persist的区别: def persist(newLevel: StorageLevel): this.type = { if (storage ...

  4. Java学习笔记之&equals;&equals;与equals

    一.问题引入 Java测试两个变量是否相等有两种方式:==运算符和equals方法. 但是这二者完全一样吗?考虑下面程序: public class TestEqual { public static ...

  5. Lucence&period;net索引技术 二

    一. Lucene索引创建和优化 [版本2.9.0以上] Lucene索引的创建首先需要取得几个必须的对象: 1.分词器//可以采用其他的中文分词器 StandardAnalyzer analyzer ...

  6. vue2&period;0 如何在hash模式下实现微信分享

    最近又把vue的demo拿出来整理下,正好要做"微信分享"功能,于是遇到新的问题: 由于hash模式下,带有"#",导致微信分享的签证无效:当改成history ...

  7. &lbrack;Python&rsqb;print vs sys&period;stdout&period;write

    之前只是在项目中看到过,没怎么注意,正好跟对象一起看python学习手册,看到了这个部分于是来研究下. python版本 2.7.x os  win7 print  一般就是执行脚本的时候,把信息直接 ...

  8. RabbitMQ学习笔记(三) 发布与订阅

    发布与订阅 在我们使用手机发送消息的时候,即可以选择给单个手机号码发送消息,也可以选择多个手机号码,群发消息. 前面学习工作队列的时候,我们使用的场景是一个消息只能被一个消费者程序实例接收并处理,但是 ...

  9. 一对多Excel自定义函数:SVLOOKUP

    语法规则 该函数的语法规则如下: SVLOOKUP(lookup_value,table_array,col_index_num,nth_appearance,unique_value) 参数 简单说 ...

  10. JS --- 本地保存localStorage、sessionStorage用法总结

    JS的本地保存localStorage.sessionStorage用法总结 localStorage.sessionStorage是Html5的特性,IE7以下浏览器不支持 为什么要掌握localS ...