【AcWing题解/洛谷题解/USACO题解】P1948 Telephone Lines S 通信线路

题目链接

AcWing：https://www.acwing.com/problem/content/description/342/
洛谷：https://www.luogu.com.cn/problem/P1948

前置知识

1.1.1.二分法和二分答案
2.2.2.单源最短路、双端队列宽度优先搜索

思路分析

本题解的设问主要依据AcWing的翻译所作.

第一部分：从设问开始——二分法的框架

设问中强调，需要支付的费用是最昂贵的那一条，同时，又强调要使最小，即求最大值的最小值，所以采用二分法。

二分法中，我们需要得到一个满足题目要求的性质。设二分得到的中间值为xxx，题目要求指定路径上不超过kkk条电缆，则我们就需要判断费用大于xxx的电缆总数是否小于等于kkk。如果费用大于xxx的电缆总数超过kkk，则说明我就算全部都免费升级费用大于xxx的电缆，也会在该部分存在电缆不免费升级，那么当前中间值xxx就不是剩下电缆中最昂贵的，不符合题意。

对于二分法中的左右边界，虽然电缆费用的范围为111到10610^6106，但是如果当前数据无解，我们会二分到右边界，如果有解，仍然有可能会到右边界，为了区分这样的情况，我们把二分的左右边界设为000和106+110^6+1106+1。

若x≤kx≤kx≤k，则满足性质，将midmidmid继续往前半部分推移；否则不满足性质，往后半部分推移。

第二部分：性质的判定——最短路的结合

如何判定其是否满足性质呢？

我们可以设费用大于xxx的电缆权值为1，设费用小于等于xxx的电缆权值为0，再做最短路算法，这样就可以算出最少需要有多少电缆费用大于xxx了。如果到达点NNN时的距离dis[N]dis[N]dis[N]小于等于kkk，则说明电缆数不超过kkk条。

对于边权值只有000和111的最短路，我们可以使用双端队列BFS。

AC代码

细节上的注意点已经写入注释。

#include<iostream>#include<cstdio>#include<cstring>#include<deque>usingnamespacestd;//注意点1：边要开两倍空间，因为是双向边constintN=1100,M=2e4+10,INF=0x3f3f3f3f;intn,m,k;inte[M],ne[M],h[N],w[M],idx;intst[N],dis[N];deque<int>q;voidadd(inta,intb,intc){w[idx]=c;e[idx]=b;ne[idx]=h[a];h[a]=idx++;return;}boolcheck(intx){//注意点2：st数组一定要记得初始化memset(st,0,sizeofst);memset(dis,INF,sizeofdis);dis[1]=0;q.push_back(1);while(!q.empty()){intnow=q.front();q.pop_front();if(st[now])continue;st[now]=true;for(inti=h[now];i!=-1;i=ne[i]){intj=e[i],v=w[i]>x;if(dis[j]>dis[now]+v){dis[j]=dis[now]+v;if(!v)q.push_front(j);elseq.push_back(j);}}}returndis[n]<=k;}intmain(){//注意点3：头数组也一定要初始化memset(h,-1,sizeofh);scanf("%d%d%d",&n,&m,&k);for(inti=1;i<=m;i++){inta,b,c;scanf("%d%d%d",&a,&b,&c);add(a,b,c);add(b,a,c);}intl=0,r=1e6+1;while(l<r){intmid=l+r>>1;if(check(mid))r=mid;elsel=mid+1;}if(r==1e6+1)printf("-1");elseprintf("%d",r);return0;}