关键词：
题目描述
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 the cables required to connect his farm to the phone system.
There are N (1 ≤ N ≤ 1,000) forlorn telephone poles conveniently numbered 1..N that are scattered around Farmer John‘s property; no cables connect any them. A total of P (1 ≤ P ≤ 10,000) pairs of poles can be connected by a cable; the rest are too far apart.
The i-th cable can connect the two distinct poles Ai and Bi, with length Li (1 ≤ Li ≤ 1,000,000) units if used. The input data set never names any {Ai, Bi} pair more than once. Pole 1 is already connected to the phone system, and pole N is at the farm. Poles 1 and N need to be connected by a path of cables; the rest of the poles might be used or might not be used.
As it turns out, the phone company is willing to provide Farmer John with K (0 ≤ K < N) lengths of cable for free. Beyond that he will have to pay a price equal to the length of the longest remaining cable he requires (each pair of poles is connected with a separate cable), or 0 if he does not need any additional cables.
Determine the minimum amount that Farmer John must pay.
多年以后，笨笨长大了，成为了电话线布置师。由于地震使得某市的电话线全部损坏，笨笨是负责接到震中市的负责人。该市周围分布着N(1<=N<=1000)根据1……n顺序编号的废弃的电话线杆，任意两根线杆之间没有电话线连接，一共有p(1<=p<=10000)对电话杆可以拉电话线。其他的由于地震使得无法连接。
第i对电线杆的两个端点分别是ai,bi，它们的距离为li(1<=li<=1000000)。数据中每对(ai,bi)只出现一次。编号为1的电话杆已经接入了全国的电话网络，整个市的电话线全都连到了编号N的电话线杆上。也就是说，笨笨的任务仅仅是找一条将1号和N号电线杆连起来的路径，其余的电话杆并不一定要连入电话网络。
电信公司决定支援灾区免费为此市连接k对由笨笨指定的电话线杆，对于此外的那些电话线，需要为它们付费，总费用决定于其中最长的电话线的长度(每根电话线仅连接一对电话线杆)。如果需要连接的电话线杆不超过k对，那么支出为0.
请你计算一下，将电话线引导震中市最少需要在电话线上花多少钱？
输入输出格式
输入格式：输入文件的第一行包含三个数字n,p,k;
第二行到第p+1行，每行分别都为三个整数ai,bi,li。
输出格式：一个整数，表示该项工程的最小支出，如果不可能完成则输出-1.
输入输出样例
Solution
思路其实不难，先二分一个答案M，那么大于M的边长变为1，小于等于的变为0，然后用最短路算出1到N的距离，如果大于K（有
超过K的路大于M）那么就不行，否则可以。直至找到答案。
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int cnt,head[1005],n,k,p;
long long dis[20005];
long long que[20005],hea,tail;
bool cl[20005];
struct road
{
int to,next,w,w2;
}e[20005];
void add(int x,int y,int z)
{
cnt++;
e[cnt].to=y;
e[cnt].w=z;
e[cnt].next=head[x];
head[x]=cnt;
}
void SPFA(int x)
{
memset(cl,0,sizeof(cl));
for(int i=1;i<=n;i++)
dis[i]=2147483647;
hea=0;
tail=1;
que[tail]=x;
dis[x]=0;
cl[x]=1;
do
{
hea++;
int u=que[hea];
cl[u]=0;
for(int i=head[u];i!=0;i=e[i].next)
{
int v=e[i].to;
if(e[i].w2+dis[u]<dis[v])
{
dis[v]=dis[u]+e[i].w2;
if(!cl[v])
{
tail++;
que[tail]=v;
cl[v]=1;
}
}
}
}while(hea<tail);
return ;
}
bool check(int m)
{
for(int i=1;i<=cnt;i++)
if(e[i].w<=m) e[i].w2=0;
else e[i].w2=1;
SPFA(1);
// for(int i=1;i<=n;i++)
// cout<<dis[i]<<‘ ‘;
// cout<<endl;
if(dis[n]>k) return 0;
else return 1;
}
int main()
{
int l,r,m;
l=0;
r=0;
cin>>n>>p>>k;
for(int i=1;i<=p;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
r=max(r,z);
add(x,y,z);
add(y,x,z);
}
int ans;
bool t=0;
while(l<=r)
{
m=(l+r)/2;
if(!check(m)) l=m+1;
else {ans=m; t=1;r=m-1;}
}
if(!t) cout<<-1;
else cout<<ans;
return 0;
}
洛谷p1948[usaco08jan]电话线telephonelines
题目描述FarmerJohnwantstosetupatelephonelineathisfarm.Unfortunately,thephonecompanyisuncooperative,soheneedstopayforsomeofthecablesrequiredtoconnecthisfarmtothephonesystem.ThereareN(1≤N≤1,000)forlorntelep 查看详情
p1948[usaco08jan]电话线telephonelines(代码片段)
P1948[USACO08JAN]电话线TelephoneLines最短路spfa暴力分层spfa。没了。（luogu数据太水，正解二分+spfa都没用上）#include<iostream>#include<cstdio>#include<cstring>#include<queue>#include<cctype>usingnames 查看详情
p1948[usaco08jan]电话线telephonelines(代码片段)
P1948[USACO08JAN]电话线TelephoneLines题目描述多年以后，笨笨长大了，成为了电话线布置师。由于地震使得某市的电话线全部损坏，笨笨是负责接到震中市的负责人。该市周围分布着N(1<=N<=1000)根据1……n顺序编号的废弃的电话线... 查看详情
p1948[usaco08jan]电话线telephonelines(代码片段)
传送门最短路二分+SPFA二分最小支出如果边权<=最小支出，那么就相当于0如果大于最小支出，值设为1跑SPFA如果dis[n]>k说明到不了否则说明可以到模板套进去就好了，没什么好注释的...#include<iostream>#include<cstdio>#include... 查看详情
p1948[usaco08jan]电话线telephonelinesspfa二分答案(代码片段)
多年以后，笨笨长大了，成为了电话线布置师。由于地震使得某市的电话线全部损坏，笨笨是负责接到震中市的负责人。该市周围分布着N(1<=N<=1000)根据1……n顺序编号的废弃的电话线杆，任意两根线杆之间没有... 查看详情
题解gup1948[usaco08jan]电话线telephonelines(代码片段)
...为什么，我就是受害者qwq你会发现最终的费用是由最长的电话线决定的，而非电话线长度和。至此就有了一个基本思路——枚举（二分）出可能的最长电话线长度，然后对其进行dij判断。dij思路如下：1.已知枚举出了假定答案ans... 查看详情
洛谷p2025脑力大人之监听电话
...下来的加赛，加赛中的前2%将进入下一轮。欢迎您收看有洛谷卫视重磅推出的综合性文艺知识类 查看详情
无线通讯网洛谷
题目描述国防部计划用无线网络连接若干个边防哨所。2种不同的通讯技术用来搭建无线网络；每个边防哨所都要配备无线电收发器；有一些哨所还可以增配卫星电话。任意两个配备了一条卫星电话线路的哨所（两边都?有卫星电... 查看详情
洛谷p1991无线通讯网(代码片段)
P1991无线通讯网题目描述国防部计划用无线网络连接若干个边防哨所。2种不同的通讯技术用来搭建无线网络；每个边防哨所都要配备无线电收发器；有一些哨所还可以增配卫星电话。任意两个配备了一条卫星电话线路的哨所（两... 查看详情
triangularpasturespoj-1948
TriangularPasturesPOJ-1948sum表示木条的总长。a[i]表示第i根木条长度。ans[i][j][k]表示用前i条木条，摆成两条长度分别为j和k的边是否可能。那么ans[i][j][k]=ans[i-1][j-a[i]][k]||ans[i-1][j][k-a[i]]可以用滚动数组优化。最后在ans[n]中枚举i和j，如... 查看详情
洛谷p1727计算π
P1727计算π题目背景《爱与愁的故事第二弹·compute》第一章。题目描述中秋至，博饼声铿锵不断。爱与愁大神兴致勃勃地到学校博饼，结果抱回家的只有一秀二举。爱与愁大神十分生气，打电话给月落乌啼：“喂，帮我... 查看详情
最小生成树+并查集(洛谷p1991无线通讯网)
题目描述国防部计划用无线网络连接若干个边防哨所。2种不同的通讯技术用来搭建无线网络；每个边防哨所都要配备无线电收发器；有一些哨所还可以增配卫星电话。任意两个配备了一条卫星电话线路的哨所（两边都?有卫星电... 查看详情
洛谷p1991无线通讯网label：最小生成树||二分
题目描述国防部计划用无线网络连接若干个边防哨所。2种不同的通讯技术用来搭建无线网络；每个边防哨所都要配备无线电收发器；有一些哨所还可以增配卫星电话。任意两个配备了一条卫星电话线路的哨所（两边都?有卫星电... 查看详情
ck1948-炼数数据分析与spss(完整)共12周
CK1948-炼数数据分析与SPSS(完整)共12周随笔背景：在很多时候，很多入门不久的朋友都会问我：我是从其他语言转到程序开发的，有没有一些基础性的资料给我们学习学习呢，你的框架感觉一下太大了，希望有个循序渐进的教程或... 查看详情
poj-1948二维01背包
T了两发,DP方程很简单粗暴dp[i][j][k]:用前i物品使得容量分别为j和k的背包恰好装满背包的调用只需一次即可,第一次T就是每次check都丧心病狂地背包一次对于sum的枚举,其实ij枚举到sum/2就可以了#include<cstdio>#include<cstring>#incl... 查看详情
洛谷1602sramoc问题
Description话说员工们整理好了筷子之后，就准备将快餐送出了，但是一看订单，都傻眼了:订单上没有留电话号码,只写了一个sramoc（k，m）函数，这什么东西？什么意思？于是餐厅找来了资深顾问团的成员,YQ,SC,HQ，经过大量的查阅... 查看详情
洛谷——p1608路径统计
https://www.luogu.org/problem/show?pid=1608题目描述“RP餐厅”的员工素质就是不一般，在齐刷刷的算出同一个电话号码之后，就准备让HZH,TZY去送快餐了，他们将自己居住的城市画了一张地图，已知在他们的地图上，有N个地方，而... 查看详情
csu1948:超级管理员(费用流)
Description长者对小明施加了膜法，使得小明每天起床就像马丁的早晨一样。今天小明早上醒来发现自己成了一位仓管员。仓库可以被描述为一个n?×?m的网格，在每个网格上有几个箱子（可能没有）。为了防止倾倒，每个网格上，... 查看详情