AcWing 340. 通信线路（二分答案+dijkstra）

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 340. 通信线路（二分答案+dijkstra）原题链接中等

作者：

Tenshi , 2021-02-19 20:33:04 , 所有人可见 , 阅读 3464

47

13

分析

题目就是要我们求所有从 $1\to n$ 的路径中第 $k+1$ 大的边的最小值。

首先考虑到搜出所有路径再找最小值，但发现数据规模太大，做不了。
于是我们可以从最小值入手，也就是采取二分答案，利用二分将这个值求出来。

假设我们二分出一个值x，那意味着x应该满足：从 $1 \to n$ 的路径中应该存在一条路，使得这条路上最多有 $k$ 条大于x的边。（二分值需要满足的属性）

那么如何刻画这个属性呢？
可以着眼于图上的边权是否大于x，如果大于，则贡献是 $1$,否则是 $0$，那么题目就转化为最短路问题。这里采用 $\texttt{dijkstra}$ 算法来求。

#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> PII;
const int N=1005,M=1e4+5;

struct node{
    int to,w,next;
}e[M<<1];
int head[N],tot;
void add(int u,int v,int w){e[tot].to=v;e[tot].w=w;e[tot].next=head[u];head[u]=tot++;}
int d[N];
bool vis[N];
int n,m,k;

bool dijk(int w){
    memset(d,0x3f,sizeof d);
    memset(vis,false,sizeof vis);
    d[1]=0;

    priority_queue<PII,vector<PII>,greater<PII> > pque;
    pque.push({0,1});

    while(pque.size()){
        auto hd=pque.top(); pque.pop();

        int ver=hd.second;
        if(vis[ver]) continue;
        vis[ver]=true;

        for(int i=head[ver];~i;i=e[i].next){
            int go=e[i].to;
            if(d[go]>d[ver]+(e[i].w>w?1:0)){ // 如果是，贡献就是1
                d[go]=d[ver]+(e[i].w>w?1:0);
                pque.push({d[go],go});
            }
        }
    }

    return d[n]<=k;
}

int main(){
    memset(head,-1,sizeof head);

    cin>>n>>m>>k;

    while(m--){
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w); add(v,u,w);
    }

    //binary search
    int l=0,r=1e6+1; //这里有个技巧，因为题目边的范围在1e6内，如果二分答案超过它，说明不存在1->n的路径
    while(r>l){
        int mid=r+l>>1;
        if(dijk(mid)) r=mid;
        else l=mid+1;
    }

    if(r!=1e6+1) cout<<r<<endl;
    else cout<<-1<<endl;

    return 0;
}

UPD：2022. 8. 22

非常感谢 @备战NOIP版的XXR 指出可以使用双端队列优化一个 $log$：

下面提供双端队列版本的代码，可以发现效率高了不少。

#include<bits/stdc++.h>
using namespace std;

const int N=1005, M=1e4+5;

struct Edge{
    int to, w, next;
}e[M<<1];

int h[N], tot;

void add(int u, int v, int w){
    e[tot].to=v, e[tot].w=w, e[tot].next=h[u], h[u]=tot++;
}

int d[N];
bool vis[N];
int n, m, k;

bool dijk(int lim){
    memset(d, 0x3f, sizeof d);
    memset(vis, false, sizeof vis);
    d[1]=0;
    deque<int> q;
    q.push_back(1);

    while(q.size()){
        int u=q.front(); q.pop_front();
        if(vis[u]) continue;
        vis[u]=true;

        for(int i=h[u]; ~i; i=e[i].next){
            int go=e[i].to;
            if(d[go]>d[u]+(e[i].w>lim)){
                d[go]=d[u]+(e[i].w>lim);
                if(e[i].w>lim) q.push_back(go);
                else q.push_front(go);
            }
        }
    }

    return d[n]<=k;
}

int main(){
    memset(h, -1, sizeof h);
    cin>>n>>m>>k;

    while(m--){
        int u, v, w; cin>>u>>v>>w;
        add(u, v, w), add(v, u, w);
    }

    //binary search
    int l=0, r=1e6+1;
    while(r>l){
        int mid=r+l>>1;
        if(dijk(mid)) r=mid;
        else l=mid+1;
    }

    if(r!=1e6+1) cout<<r<<endl;
    else cout<<-1<<endl;

    return 0;
}

23 评论

CZL 2021-07-02 23:22

看了你的终于会做了

聰cy 9个月前

上面是dijkstra，下面是spfa吧

幻顾 9个月前

下面是双端队列😄

菟誊 2023-07-03 22:46

我有个疑问就是当二分枚举的答案能在1到N的路径中找到<= k的边数，此时该答案应该是可以继续二分的，但如果
所有边中都没有为x的边权这样是不是二分从本质上就错了

小宇_76 2024-01-12 16:23

我有这个疑问，然后因为我写错了输出，输出了mid结果比原本答案的小了1，我以为是因为我找到的这个边原本就不存在于图中。虽然最后找到了错的是写成输出mid了，但是我感觉确实会有这种可能，就是我们找到了一个不存在图中的一个最终边权，但是又有小于等于k个边比他大的。然后我们就会错误的输出这个不存在的边权。

退役账户 8个月前

一定会有的

ttdykdy 4个月前

对
但是，你做二分的题目时肯定是从所有可能的情况来取l和r

Hikario 2023-05-21 14:44

看了您的思路写了份代码，但是在第三个点WA了QAQ
找半天找不到问题QwQ
大佬能帮我看看吗Orz

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
#define int long long
const int N=2e5+20;
int n,p,k,idx;
int e[N],ne[N],h[N],w[N],ww[N],dist[N];
bool vis[N],st[N];
typedef pair<int,int> PII;
inline void add(int a,int b,int c)
{
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
inline void dfs(int id,int maxn)
{
    for(int i=h[id],j;~i;i=ne[i])
    {
        j=e[i];
        if(vis[i])continue;
        if(w[i]>maxn)ww[i]=1;
        vis[i]=true;
        dfs(j,maxn);
    }
}
inline int Dijkstra()
{
    memset(dist,0x3f,sizeof dist);
    memset(st,0,sizeof st);
    priority_queue<PII,vector<PII>,greater<PII> >q;
    dist[1]=0;
    q.push({0,1});
    while(q.size())
    {
        PII temp=q.top();
        q.pop();
        int lenth=temp.first,num=temp.second;
        if(st[num])continue;
        st[num]=true;
        for(int i=h[num],j;i!=-1;i=ne[i])
        {
            j=e[i];
            if(dist[j]>lenth+ww[i])dist[j]=lenth+ww[i],q.push({dist[j],j});
        }
    }
    return dist[n];
}
signed main()
{
    memset(h,-1,sizeof h);
    cin>>n>>p>>k;
    int t,tt,ttt,l=0x3f3f3f3f,r=-1,mid,ret;
    for(int i=1;i<=p;i++)
    {
        scanf("%lld%lld%lld",&t,&tt,&ttt);
        add(t,tt,ttt),add(tt,t,ttt);
        l=min(l,ttt),r=max(r,ttt);
    }       
    while(l<=r)
    {
        mid=l+r>>1;
        memset(ww,0,sizeof ww);
        memset(vis,0,sizeof vis);
        dfs(1,mid);
        int t=Dijkstra();
        if(t==0x3f3f3f3f)return puts("-1"),0;
        if(t<=1)r=mid-1,ret=mid;
        else l=mid+1;
    }
    cout<<ret<<endl;
    return 0;
}

Xile 2022-08-22 12:51

双端队列优化会不会更快？

Xile 2022-08-22 12:52

这样省去了一个logN

Tenshi 2022-08-22 13:07 回复了 Xile 的评论

可以的，效率高了不少，已在题解更新 deque 的做法，谢谢指出😄

有机物 2022-08-13 23:22

Tenshi 2022-08-14 13:28

/jk

做ac梦w 2022-06-13 21:01

想问下二分出来的值不是路径上的值怎么办呀

Tenshi 2022-06-14 22:54

没关系，因为最后二分出来的结果一定是路径上的值

Paraline 2023-05-04 17:13

直接把所有边权排序，直接对边权二分也行

等等_53 10个月前回复了 Tenshi 的评论

为什么一定是路径上的值呀

晒干了沉默 2022-05-12 22:12

肥肠nice看了你的立马会了

.拾光. 2022-03-28 20:09

强orz

KobeBryant24 2022-03-24 12:02

朴素版写法为什么不行呀？

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N = 1010;
bool vis[N];
int dis[N];
int G[N][N];
int n, p, k;

bool checkByDijkstra(int cost){
    memset(dis, 0x3f, sizeof dis);
    memset(vis, 0, sizeof vis);
    dis[1] = 0;
    for(int i = 1; i <= n; ++i){
        int t = -1;
        for(int j = 1; j <= n; ++j)
            if(!vis[j] && (t == -1 || dis[t] > dis[j]))
                t = j;
        vis[t] = true;
        for(int i = 1; i <= n; ++i){
            int w = G[t][i] > cost ? 1 : 0;
            if(dis[i] > (dis[t] + w))
                dis[i] = dis[t] + w;
        }
    }
    return dis[n] <= k;
}



// bool checkByDijkstra(int cost){
//     memset(dis, 0x3f, sizeof dis);
//     memset(vis, 0, sizeof vis);
//     dis[1] = 0;
//     priority_queue<PII, vector<PII>, greater<PII>> heap;
//     heap.push({0, 1});
//     while(heap.size()){
//         auto t = heap.top();
//         heap.pop();
//         int curId = t.y, curDis = t.x;
//         if(vis[curId])  continue;
//         vis[curId] = true;
//         for(int i = 1; i <= n; ++i){
//             if(G[curId][i] != 0x3f3f3f3f){
//                 if(dis[i] > dis[curId] + (G[curId][i] > cost ? 1 : 0)){
//                     dis[i] = dis[curId] + (G[curId][i] > cost ? 1 : 0);
//                     heap.push({dis[i], i});
//                 }
//             }
//         }
//     }
//     return dis[n] <= k;
// }

int main(){
    cin >> n >> p >> k;
    memset(G, 0x3f, sizeof G);
    for(int i = 0; i < p; ++i){
        int x, y, z;
        cin >> x >> y >> z;
        G[x][y] = G[y][x] = z;
    }
    int l = 0, r = 1e6+1;
    while(l < r){
        int mid = (l + r) >> 1;
        if(checkByDijkstra(mid))  r = mid;
        else    l = mid + 1;
    }
    if(r == 1e6+1)    puts("-1");
    else    cout << r << endl;
    return 0;
}

Tenshi 2022-03-24 17:43

帮你调过了：
需要注意，一个点必须要与另一个点联通才能去更新它的距离。
见代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N = 1010;
bool vis[N];
int dis[N];
int G[N][N];
int n, p, k;

bool checkByDijkstra(int cost){
    memset(dis, 0x3f, sizeof dis);
    memset(vis, 0, sizeof vis);
    dis[1] = 0;
    for(int i = 1; i <= n; ++i){
        int t = -1;
        for(int j = 1; j <= n; ++j)
            if(!vis[j] && (t == -1 || dis[t] > dis[j]))
                t = j;

        vis[t] = true;
        for(int i = 1; i <= n; ++i) if(G[t][i]!=0x3f3f3f3f){ // 保证联通才可以
            int w = G[t][i] > cost ? 1 : 0;
            if(dis[i] > (dis[t] + w))
                dis[i] = dis[t] + w;
        }
    }
    return dis[n] <= k;
}

int main(){
    cin >> n >> p >> k;
    memset(G, 0x3f, sizeof G);
    for(int i = 0; i < p; ++i){
        int x, y, z;
        cin >> x >> y >> z;
        G[x][y] = G[y][x] = z;
    }
    int l = 0, r = 1e6+1;
    while(l < r){
        int mid = (l + r) >> 1;
        if(checkByDijkstra(mid))  r = mid;
        else    l = mid + 1;
    }
    if(r == 1e6+1)    puts("-1");
    else    cout << r << endl;
    return 0;
}

KobeBryant24 2022-03-24 19:16 回复了 Tenshi 的评论

orz 谢谢你！

终有一天 2021-06-16 15:13

tql，你是讲的最清楚的

App 内打开

AcWing 340. 通信线路（二分答案+dijkstra） 原题链接 中等

分析

23 评论

AcWing 340. 通信线路（二分答案+dijkstra）原题链接中等