bzoj 1614: [Usaco2007 Jan]Telephone Lines架设电话线

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

Sample Output

HINT

Source

Silver

好久没上图片了

就很开心

这道题就很骚

刚开始以为直接最小生成树就可以了

后来发现

假设k=9

有两种从1到n的方案

一种十条2，另一种九条9和一条1

最小生成树会选择第一种

而最优的是第二种（把那九条9置为0）

所以我们想到可以二分最长路径的长度（套路）（然而我并没有想到QAQ）

如果边的长度大于mid，我们把它设成1

否则，为0

然后跑spfa

如果dis[n]>k，则不符合条件

反之则符合

#include
#include
const int M=10000+7,N=1007,len=1e5;
struct node
{int to,next,c,dis;
}e[M*2];
int cnt;
int first[N];
int qu[len+7],dis[N],visit[N];
void insert(int u,int v,int c)
{e[++cnt]=(node){v,first[u],c,0};first[u]=cnt;e[++cnt]=(node){u,first[v],c,0};first[v]=cnt;
}
void spfa()
{memset(dis,127,sizeof(dis));qu[1]=1;visit[1]=1;dis[1]=0;int head=1,tail=2;while(head!=tail){int rr=qu[head++];if(head==len)	head=0;for(int k=first[rr];k;k=e[k].next)if(dis[e[k].to]>dis[rr]+e[k].dis){dis[e[k].to]=dis[rr]+e[k].dis;if(!visit[e[k].to]){if(dis[qu[head]]>dis[e[k].to]){head--;if(head<0)	head=len-1;qu[head]=e[k].to;}else{qu[tail++]=e[k].to;if(tail==len)	tail=0;}}}visit[rr]=0;}}
void work(int mid)
{for(int i=1;i<=cnt;i++){if(e[i].c>mid)	e[i].dis=1;else e[i].dis=0;}spfa();
}
int main()
{int n,p,k;scanf("%d %d %d",&n,&p,&k);for(int i=1;i<=p;i++){int u,v,q;scanf("%d %d %d",&u,&v,&q);insert(u,v,q);}int ll=0,rr=1000000;while(rr-ll>1){int mid=(ll+rr)>>1;work(mid);
//		printf("std::%d %d\n",dis[n],mid);if(dis[n]>k)	ll=mid+1;else rr=mid;}work(ll);if(dis[n]>k){work(rr);if(dis[n]>k)	ll=-1;else ll=rr;}printf("%d\n",ll);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！