首页 > 代码库 > BZOJ1614: [Usaco2007 Jan]Telephone Lines架设电话线
BZOJ1614: [Usaco2007 Jan]Telephone Lines架设电话线
1614: [Usaco2007 Jan]Telephone Lines架设电话线
Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 892 Solved: 399
[Submit][Status]
Description
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最少需要在电话线上花多少钱。
Input
* 第1行: 3个用空格隔开的整数:N,P,以及K
* 第2..P+1行: 第i+1行为3个用空格隔开的整数:A_i,B_i,L_i
Output
* 第1行: 输出1个整数,为FJ在这项工程上的最小支出。如果任务不可能完成, 输出-1
Sample Input
5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6
输入说明:
一共有5根废弃的电话线杆。电话线杆1不能直接与电话线杆4、5相连。电话
线杆5不能直接与电话线杆1、3相连。其余所有电话线杆间均可拉电话线。电信
公司可以免费为FJ连结一对电话线杆。
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6
输入说明:
一共有5根废弃的电话线杆。电话线杆1不能直接与电话线杆4、5相连。电话
线杆5不能直接与电话线杆1、3相连。其余所有电话线杆间均可拉电话线。电信
公司可以免费为FJ连结一对电话线杆。
Sample Output
4
输出说明:
FJ选择如下的连结方案:1->3;3->2;2->5,这3对电话线杆间需要的
电话线的长度分别为4、3、9。FJ让电信公司提供那条长度为9的电话线,于是,
他所需要购买的电话线的最大长度为4。
输出说明:
FJ选择如下的连结方案:1->3;3->2;2->5,这3对电话线杆间需要的
电话线的长度分别为4、3、9。FJ让电信公司提供那条长度为9的电话线,于是,
他所需要购买的电话线的最大长度为4。
HINT
Source
Silver
题解:
好吧是二分。这种题目和二分好像都差不多有点儿关系?
代码:
1 uses math; 2 const maxn=1000+200; 3 type node=record 4 go,next,w:longint; 5 end; 6 var d,head:array[0..maxn] of longint; 7 v:array[0..maxn] of boolean; 8 q:array[0..10*maxn] of longint; 9 e:array[0..20000] of node;10 i,n,m,k,l,r,x,y,z,mid,tot,ll,rr:longint;11 procedure insert(x,y,z:longint);12 begin13 inc(tot);14 e[tot].go:=y;e[tot].w:=z;e[tot].next:=head[x];head[x]:=tot;15 end;16 17 function spfa(val:longint):boolean;18 var i,x,y,tmp:longint;19 begin20 fillchar(d,sizeof(d),60);21 fillchar(v,sizeof(v),false);22 l:=0;r:=1;q[1]:=1;d[1]:=0;v[1]:=true;23 while l<r do24 begin25 l:=l+1;26 x:=q[l];v[x]:=false;27 i:=head[x];28 while i<>0 do29 begin30 y:=e[i].go;31 if e[i].w>val then tmp:=d[x]+1 else tmp:=d[x];32 if tmp<d[y] then33 begin34 d[y]:=tmp;35 if not(v[y]) then36 begin37 v[y]:=true;38 r:=r+1;39 q[r]:=y;40 end;41 end;42 i:=e[i].next;43 end;44 end;45 exit(d[n]<=k);46 end;47 procedure init;48 begin49 readln(n,m,k);50 for i:=1 to m do51 begin52 readln(x,y,z);53 insert(x,y,z);insert(y,x,z);54 end;55 end;56 procedure main;57 begin58 ll:=0;rr:=1000000+1;59 while ll<rr do60 begin61 mid:=(ll+rr)>>1;62 if spfa(mid) then rr:=mid else ll:=mid+1;63 end;64 if ll>1000000 then writeln(‘-1‘) else writeln(ll);65 end;66 67 begin68 assign(input,‘input.txt‘);assign(output,‘output.txt‘);69 reset(input);rewrite(output);70 init;71 main;72 close(input);close(output);73 end.
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。