原题链接 https://www.luogu.org/problem/P1948
给你一个无向图，让你去掉 k 条边后求 1~n 所经过路径中的最大边最小是多少 。
看到这个问法，是二分没错了！关键是怎么二分 。
按照一般的套路，我们直接二分答案，那么这里就二分这个最大边！
既然我们二分的这条边是最小的最大边，也就是说不会再经过任何比这条边还大的边了；
为了防止经过那些比它大的边，我们可以利用那 k 次免费机会 。
一个炒鸡敲庙的思路：
我们将所有比我们二分出来的这条边大的边的值暂时赋成 1，其余的赋成 0（代码里用 now 表示），我们从点 1 跑一次最短路，那么 dis [ n ] 就是从 1 到 n 所花费的最少免费次数 。
判断我们二分的这一条边是否合法，就可以看看 dis [ n ] 和 k 的大小关系：
如果 dis [ n ] <= k，说明这是一个合法的方案，我们可以继续往小里二分；否则要往大里二分！
其实也不是很难嘛qwq
#include<iostream> #include<cstdio> #include<cmath> #include<queue> #include<cstring> using namespace std; int read() { char ch=getchar(); int a=0,x=1; while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) x=-x; ch=getchar(); } while(ch>=‘0‘&&ch<=‘9‘) { a=(a<<1)+(a<<3)+(ch-‘0‘); ch=getchar(); } return a*x; } const int inf=1e9; int n,m,k,l,r,ans,edge_sum; int u[10001],v[10001],w[10001],dis[10001],vis[10001],head[10001]; struct node { int now,dis,from,to,next; //now是存这条边和我们二分的mid的大小关系的,不懂的往下看看就好了 }a[100001]; void add(int from,int to,int dis) //链表建边 { edge_sum++; a[edge_sum].from=from; a[edge_sum].to=to; a[edge_sum].dis=dis; a[edge_sum].next=head[from]; head[from]=edge_sum; } bool check(int x) //SPFA判断合法性 { queue<int> q; for(int i=1;i<=n;i++) //注意初始化 { dis[i]=inf; vis[i]=0; } for(int i=1;i<=edge_sum;i++) { if(a[i].dis>x) a[i].now=1; //把比mid大的边设为1 else a[i].now=0; //其他的设为0 } dis[1]=0; q.push(1); vis[1]=0; while(!q.empty()) { int f=q.front(); q.pop(); vis[f]=0; for(int i=head[f];i;i=a[i].next) { int zd=a[i].to; if(dis[zd]>dis[f]+a[i].now) //注意这里用到的是now { dis[zd]=dis[f]+a[i].now; if(!vis[zd]) { vis[zd]=1; q.push(zd); } } } } if(dis[n]<=k) return 1; //看看用的免费次数是否小于k else return 0; } int main() { n=read();m=read();k=read(); //n个点,m条边,k次免费机会 l=1e9; for(int i=1;i<=m;i++) { u[i]=read();v[i]=read();w[i]=read(); add(u[i],v[i],w[i]); //注意建双向边 add(v[i],u[i],w[i]); l=min(l,w[i]); //找二分枚举的上下界 r=max(r,w[i]); } while(l<=r) //二分答案 { int mid=(l+r)>>1; if(check(mid)) r=mid-1,ans=mid; else l=mid+1; } if(ans==0) printf("-1"); //如果没有找到答案,就是无解 else printf("%d",ans); return 0; }
P1948 [USACO08JAN]电话线Telephone Lines
原文：https://www.cnblogs.com/xcg123/p/11385403.html