「BZOJ1614」[Usaco2007 Jan] Telephone Lines架设电话线
题目描述
Farmer John打算将电话线引到自己的农场，但电信公司并不打算为他提供免费服务。于是，FJ必须为此向电信公司支付一定的费用。
FJ的农场周围分布着N(1 <= N <= 1,000)根按1..N顺次编号的废弃的电话线杆，任意两根电话线杆间都没有电话线相连。一共P(1 <= P <= 10,000)对电话线杆间可以拉电话线，其余的那些由于隔得太远而无法被连接。
第i对电话线杆的两个端点分别为A_i、B_i，它们间的距离为L_i (1 <= L_i <= 1,000,000)。数据中保证每对{A_i，B_i}最多只出现1次。编号为1的电话线杆已经接入了全国的电话网络，整个农场的电话线全都连到了编号为N的电话线杆上。也就是说，FJ的任务仅仅是找一条将1号和N号电话线杆连起来的路径，其余的电话线杆并不一定要连入电话网络。
经过谈判，电信公司最终同意免费为FJ连结K(0 <= K < N)对由FJ指定的电话线杆。对于此外的那些电话线，FJ需要为它们付的费用，等于其中最长的电话线的长度（每根电话线仅连结一对电话线杆）。如果需要连结的电话线杆不超过K对，那么FJ的总支出为0。
请你计算一下，FJ最少需要在电话线上花多少钱。
输入
* 第1行: 3个用空格隔开的整数：N，P，以及K
* 第2..P+1行: 第i+1行为3个用空格隔开的整数：A_i，B_i，L_i
输出
* 第1行: 输出1个整数，为FJ在这项工程上的最小支出。如果任务不可能完成，输出-1
样例输入
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
提示
输入说明:
一共有5根废弃的电话线杆。电话线杆1不能直接与电话线杆4、5相连。电话线杆5不能直接与电话线杆1、3相连。其余所有电话线杆间均可拉电话线。电信公司可以免费为FJ连结一对电话线杆。
输出说明:
FJ选择如下的连结方案：1->3；3->2；2->5，这3对电话线杆间需要的电话线的长度分别为4、3、9。FJ让电信公司提供那条长度为9的电话线，于是，他所需要购买的电话线的最大长度为4。
题解
二分答案，在判定是否可行时，只需要判断是否能寻找到一条路径，使得该路径上大于我们二分的这个值的边不超过k条，实质上就是最短路做的一个变形而已，小于二分的值的边可以看做边权为0，大于的可以看做边权为1，直接求最短路看是否小于k即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
#include<iostream> #include<cstdio> #include<cstring> using namespace std; struct data{int to,next,v;}e[20001]; int n,p,k,cnt,head[1001],dis[1001],q[1001],inq[1001],ans=-1; void insert(int u,int v,int w) {cnt++;e[cnt].to=v;e[cnt].v=w;e[cnt].next=head[u];head[u]=cnt;} bool spfa(int x) { memset(dis,127/3,sizeof(dis)); int t=0,w=1,i,now,s; dis[1]=0;q[t]=1;inq[1]=1; while(t!=w) { now=q[t];t++;if(t==1001)t=0; i=head[now]; while(i) { if(e[i].v>x)s=dis[now]+1; else s=dis[now]; if(s<dis[e[i].to]) { dis[e[i].to]=s; if(!inq[e[i].to]) { q[w++]=e[i].to; inq[e[i].to]=1; if(w==1001)w=0; } } i=e[i].next; } inq[now]=0; } if(dis[n]<=k)return 1; return 0; } int main() { scanf("%d%d%d",&n,&p,&k); for(int i=1;i<=p;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); insert(u,v,w);insert(v,u,w); } int l=0,r=1000000; while(l<=r) { int mid=(l+r)>>1; if(spfa(mid)){ans=mid;r=mid-1;} else l=mid+1; } printf("%d",ans); return 0; } |
计数器 9774790
OI 课件=>
OI 课件=>
请问l,r是前开后闭区间？
-1呢？？？
不可能要-1
开始时ans不是初值已经赋值成-1了