[南海云课堂] [01最短路] [二分答案] [分层图] 优惠

_Cheems · 2023-08-09 08:01:11 · 个人记录

题意

在郊区有 N 座通信基站，P 条 双向 电缆，第 i 条电缆连接基站 A_i 和 B_i。

特别地，1 号基站是通信公司的总站，N 号基站位于一座农场中。

现在，农场主希望对通信线路进行升级，其中升级第 i 条电缆需要花费 L_i。

电话公司正在举行优惠活动。

农产主可以指定一条从 1 号基站到 N 号基站的路径，并指定路径上不超过 K 条电缆，由电话公司免费提供升级服务。

农场主只需要支付在该路径上剩余的电缆中，升级价格最贵的那条电缆的花费即可。

求至少用多少钱可以完成升级。

思路

• 二分答案

  显然答案满足单调性，考虑二分答案求最贵电缆价格的 q。

  思考 check 函数：

  1. 由题意知，只需满足 1 到 n 之间存在一条路径，使得路径上比 q 贵的电缆数量不超过 k，那么 q 就是合法的。

  2. 此时我们不关注边的具体大小，因为边只有 >q/≤q 两种状态。考虑最短路算法，统计 1 到 n 最少有几条 >q 的边。

  3. 计数的准备：将 >q 的边标为 1，≤q 的边标为 0。

  4. 只需比对 1 到 n 的最短路径是否不超过 k 即可。

  • \rm{BFS} 与 0/1 最短路

    常见最短路算法（如 $\rm{Dijkstra}$、$SPFA$） 处理这类问题的复杂度在 $O(mlogn)$、$O(km)$ 左右。而 $\rm{BFS}$ 的复杂度不超过 $O(n)$。 显然，在此类问题中，每个点的路径一经确定就是最短的。换句话说在 $\rm {BFS}$ 过程中，每个点只会被遍历一次。 回顾 $\rm {BFS}$，它需维护如下性质： * **阶段性**：即队列中的所有元素都分为不同阶段，相同阶段的点紧密排列。 * **最优性**：$a$ 阶段优于 $a+1$ 阶段。放在最短路中，每个阶段的元素代表源点至一点的最短路径，因此最优性也是无后效性。 为了保证 $\rm {BFS}$ 的正确，需要维护它的最优性。 假设每次取出节点 $u$，$u$ 通过 $e(u,v)$ 更新节点 $v$，接下来要将 $v$ 入队。 我们只需在对每个入队时维护，维护方式如下： 1. 若 $w(u,v)=0$：则 $dis_v=dis_u$，$v$ 属于阶段 $a$，故将 $v$ 加入队首。 2. 若 $w(u,v)=1$：则 $dis_v=dis_u+1$，$v$ 属于阶段 $a+1$，故将 $v$ 加入队尾。

  时间复杂度为 O(n*log_2L_{max})。

• 分层图

  假如没有 k 的限制，那么跑一边最短路即可。

  运用分层思想，将问题化为共 k 层的图，元素为 (u,k)。显然每层具有相似性、层与层之间有权为 0 的边相连（使用一次免费的电缆）。

  而分层思想的关键在于建图：

  建图后直接跑一遍最短路，求出 (1,0) 到 (n,k) 的最短路即可。

  分层图共有 nk 个点、mk 条边。若使用堆优化的 \rm {Dijkstra}，那么时间复杂度为 O(mk*log_2nk)。

  分层思想的好处在于易想、好写、好调，但时空复杂度往往过高。

  代码

• 二分答案

  #include<bits/stdc++.h>
  using namespace std;
  #define pir pair<int,int>
  const int N=1e3+5,M=1e4+5;
  int n,m,k,u,v,head[N],vis[N],cnt,w,dis[N];
  struct edge{
    int v,nxt,w;
  }e[2*M];
  void add(int u,int v,int w){
    e[++cnt]={v,head[u],w};
    head[u]=cnt;
  }
  int bfs(int rt,int ma){
    memset(dis,0x3f,sizeof dis);
    memset(vis,0,sizeof vis);
    deque<pair<int,int>>q;
    dis[1]=0;
    q.push_front({dis[1],1});
    while(!q.empty()){
        int s=q.front().first;
        int u=q.front().second;
        q.pop_front();
        if(vis[u]){
            continue;
        }
        vis[u]=1;
        for(int i=head[u]; i;i=e[i].nxt){
            int v=e[i].v,w=e[i].w;
            w=(w>ma?1:0);
            if(dis[u]+w<dis[v]){
                dis[v]=dis[u]+w;
                if(w){
                    q.push_back({dis[v],v});
                }
                else{
                    q.push_front({dis[v],v});
                }
            }
        }
    }
    return dis[n];
  }
  bool check(int ma){
    if(bfs(1,ma)>k){
        return 0;
    }
    return 1;
  }
  int main(){
    cin>>n>>m>>k;
    for(int i=1; i<=m;i++){
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
    }
    int l=-1,r=1e6+5,mid;
    while(l+1<r){
        mid=(l+r)>>1;
        if(check(mid)){
            r=mid;
        }
        else{
            l=mid;
        }
    }
    if(check(r)){
        cout<<r;
    }
    else{
        cout<<-1;
    }
    return 0;
  }

• 分层图

  #include<bits/stdc++.h>
  using namespace std;
  #define pir pair<int,int>
  const int N=1e3+5,M=1e4+5,NN=2e6+5;
  int n,m,k,u,v,head[NN],vis[NN],cnt;
  int w,dis[NN],INF;
  struct edge{
    int v,nxt,w;
  }e[2*NN];
  void add(int u,int v,int w){
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].nxt=head[u];
    head[u]=cnt;
  }
  inline int id(int u,int p){
    return p*n+u+1;
  }
  void dj(int k){
    priority_queue<pir,vector<pir>,greater<pir>>q;
    memset(dis,0x3f,sizeof(dis)); 
    dis[k]=0; 
    INF=dis[0]; 
    q.push({0,k}); 
    while(!q.empty()){
        int s=q.top().first;
        int k=q.top().second;
        q.pop();
        if(vis[k]){ 
            continue;
        }
        vis[k]=1; 
        for(int i=head[k]; i;i=e[i].nxt){
            int j=e[i].v;
            if(!vis[j]&&max(dis[k],e[i].w)<dis[j]){
                dis[j]=max(dis[k],e[i].w);
                q.push({dis[j],j});
            }
        }
    }
  }
  int main(){
    cin>>n>>m>>k;
    for(int i=1; i<=m;i++){
        scanf("%d%d%d",&u,&v,&w);
        for(int j=0; j<=k;j++){
            add(id(u,j),id(v,j),w);
            add(id(v,j),id(u,j),w);
            if(j+1<=k){
                add(id(u,j),id(v,j+1),0);
                add(id(v,j),id(u,j+1),0);
            }
        }
    }
    dj(id(1,0)); 
    if(dis[id(n,k)]==INF){ 
        cout<<-1; 
    } 
    else{ 
        cout<<dis[id(n,k)];
    }
    return 0;
  }