【Acwing】最短路+二分通信线路

╰+攻爆jí腚メ 2024-03-31 09:03 66阅读 0赞

[340. 通信线路 - AcWing题库][340. _ - AcWing]

题意：

![17f01f524c01469aa192b2306a8d79f7.png][]

思路：

首先因为贪心，免费升级的肯定是最贵的那几根

因此这道题可以简化为：

给定一张图，求结点1到结点N的所有路径中第K+1大的边权的最小值

可以发现我们要求剩下的边中最大值的最小值，因此可以想到二分

**我们如何考虑二分？**

**1.先去考虑我们二分的是什么**

**2.考虑我们二分的这个东西它具不具有单调性**

**3.考虑如何去check这个二分出来的东西，我们假设已经求出了二分出来的东西，在check的时候常常考虑贪心**

对于这道题：

1.我们二分的是第K+1大的边权值

2.考虑单调性：当第K+1大的边权值足够大时，我们可以发现升级的边数就是0，当第K+1大的边权值足够小时，我们可以发现升级的边数就是总边数

考虑（需要升级的边数<=K）为合法，因此满足单调性

3.如何check？我们假设已经求出来了第K+1大的边权值，那么就是去check是否存在一条路径使得路径中大于第K+1大的边权值<=K，因此可以把大于第K+1的边权值的边设为1，小于的设为0，去跑最短路就行（这里好像可以用双端队列求，但是不会，只会最短路板子qwq）

Code：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=1e3+10,mxe=1e4+10,mnf=0x3f3f3f3f;
    struct ty{
        int to,next,w;
    }edge[mxe<<1];
    struct ty2{
        int x,dis;
        bool operator<(const ty2 &a)const{
            return a.dis<dis;
        }
    };
    priority_queue<ty2> q;
    int n,m,k,x,y,w,tot=0,ans=mnf;
    int head[mxn],dis[mxn],vis[mxn];
    void add(int u,int v,int w){
        edge[tot].w=w;
        edge[tot].to=v;
        edge[tot].next=head[u];
        head[u]=tot++;
    }
    void init(){
        tot=0;
        for(int i=0;i<=n;i++){
            vis[i]=0;
            head[i]=-1;
            dis[i]=mnf;
        }
    }
    int dij(int s,int t,int k){
        dis[s]=0;
        ty2 tmp;
        tmp.dis=0,tmp.x=s;
        q.push(tmp);
        while(!q.empty()){
            ty2 u=q.top();
            q.pop();
            if(vis[u.x]) continue;
            vis[u.x]=1;
            for(int i=head[u.x];~i;i=edge[i].next){
                if(dis[edge[i].to]>dis[u.x]+(edge[i].w>k?1:0)){
                    dis[edge[i].to]=dis[u.x]+(edge[i].w>k?1:0);
                    ty2 tmp2;
                    tmp2.dis=dis[edge[i].to];
                    tmp2.x=edge[i].to;
                    q.push(tmp2);
                }
            }
        }
        return dis[t];
    }
    void init2(){
        memset(vis,0,sizeof(vis));
        memset(dis,0x3f,sizeof(dis));
        while(!q.empty()) q.pop();
    }
    bool check(int x){
        init2();
        return dij(1,n,x)<=k;
    }
    int main(){
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        cin>>n>>m>>k;
        init();
        for(int i=1;i<=m;i++){
            cin>>x>>y>>w;
            add(x,y,w);
            add(y,x,w);
        }
        int l=0,r=1e6+1;
        while(l<=r){
            int mid=l+r>>1;
            if(check(mid)){
                ans=mid;
                r=mid-1;
            }else l=mid+1;
        }
        if(ans==mnf) ans=-1;
        cout<<ans<<'\n';
    }

**总结：**

**我们如何考虑二分？**

**1.先去考虑我们二分的是什么**

**2.考虑我们二分的这个东西它具不具有单调性**

**3.考虑如何去check这个二分出来的东西，我们假设已经求出了二分出来的东西，在check的时候常常考虑贪心**

[340. _ - AcWing]: https://www.acwing.com/problem/content/342/
[17f01f524c01469aa192b2306a8d79f7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/4040625f62904a3dab34c00dc71c2052.png