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

题目链接AcWinghttps://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和106110^611061。若x≤kx≤kx≤k则满足性质将midmidmid继续往前半部分推移否则不满足性质往后半部分推移。第二部分性质的判定——最短路的结合如何判定其是否满足性质呢我们可以设费用大于xxx的电缆权值为1设费用小于等于xxx的电缆权值为0再做最短路算法这样就可以算出最少需要有多少电缆费用大于xxx了。如果到达点NNN时的距离dis[N]dis[N]dis[N]小于等于kkk则说明电缆数不超过kkk条。对于边权值只有000和111的最短路我们可以使用双端队列BFS。AC代码细节上的注意点已经写入注释。#includeiostream#includecstdio#includecstring#includedequeusingnamespacestd;//注意点1边要开两倍空间因为是双向边constintN1100,M2e410,INF0x3f3f3f3f;intn,m,k;inte[M],ne[M],h[N],w[M],idx;intst[N],dis[N];dequeintq;voidadd(inta,intb,intc){w[idx]c;e[idx]b;ne[idx]h[a];h[a]idx;return;}boolcheck(intx){//注意点2st数组一定要记得初始化memset(st,0,sizeofst);memset(dis,INF,sizeofdis);dis[1]0;q.push_back(1);while(!q.empty()){intnowq.front();q.pop_front();if(st[now])continue;st[now]true;for(intih[now];i!-1;ine[i]){intje[i],vw[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(inti1;im;i){inta,b,c;scanf(%d%d%d,a,b,c);add(a,b,c);add(b,a,c);}intl0,r1e61;while(lr){intmidlr1;if(check(mid))rmid;elselmid1;}if(r1e61)printf(-1);elseprintf(%d,r);return0;}