telephone lines

telephone lines

题目描述

多年以后,笨笨长大了,成为了电话线布置师。由于地震使得某市的电话线全部损坏,笨笨是负责接到震中市的负责人。

该市周围分布着N(1<=N<=1000)根据1……n顺序编号的废弃的电话线杆,任意两根线杆之间没有电话线连接,一共有p(1<=p<=10000)对电话杆可以拉电话线。其他的由于地震使得无法连接。

第i对电线杆的两个端点分别是ai,bi,它们的距离为li(1<=li<=1000000)。数据中每对(ai,bi)只出现一次。编号为1的电话杆已经接入了全国的电话网络,整个市的电话线全都连到了编号N的电话线杆上。也就是说,笨笨的任务仅仅是找一条将1号和N号电线杆连起来的路径,其余的电话杆并不一定要连入电话网络。

电信公司决定支援灾区免费为此市连接k对由笨笨指定的电话线杆,对于此外的那些电话线,需要为它们付费,总费用决定于其中最长的电话线的长度(每根电话线仅连接一对电话线杆)。如果需要连接的电话线杆不超过k对,那么支出为0.

请你计算一下,将电话线引导震中市最少需要在电话线上花多少钱?

解题思路

这道题的题面简单来说就是 给你一个图,让你求一条从1号点到n号点的路径中第k+1长边最短。

这道题目就是 最短路 + 二分答案 并且每一次最短路并不是以边权作为路径长度,

而是以 0 和 1 代表是否比假设的答案大(0为小于,1为大于),并将0和1作为路径长度。

嗯,这个思路很清奇。

代码

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int n,p,k;
struct node{
    int v;
    int w;
};
struct cmp{
    bool operator () (node aa,node bb){
        return aa.w > bb.w;
    }
};
vector<node> G[1005];
int dis[1005]; //dis[i]保存从1号点到i号点的路径中比二分答案大的边数 
bool vis[1005];//保存是否访问过该节点 
bool dij(int mid){
    priority_queue<node,vector<node>,cmp> save;
    while(!save.empty()) save.pop();
    for(int i=1;i<=n;i++){
        dis[i]=10000000;
        vis[i]=0;
    }
    node cur,nxt;
    //最少有 dis[n]个 大于枚举值
    //如果记不清怎么写,就回想执行步骤
    //1.找到当前距离起点最近的点x
    //2.枚举所有和x连边的点进行松弛
    cur.v = 1;//一号节点开始 
    cur.w = 0;//一号节点到一号节点的边权为0 
    dis[1] = 0;//一号节点到一号节点的边权为0 
    save.push(cur);
    int res;//暂时用于储存某条边是否大于二分答案,1为大于,0为小于等于 
    while(!save.empty()){
        cur=save.top();//取出save数组中边权最小的元素,用这个元素“松弛” 
        save.pop();//已经用过,所以弹出
        if(vis[cur.v]) continue;//如果该节点已经用于松弛过则弹出 
        vis[cur.v] = 1;//标记使用于“松弛”过了 
        
        //以下为松弛操作:(使用vector存图)
        int Size=G[cur.v].size();//保存与该节点相连的节点数量 
        for(int i=0;i<Size;i++){
            if(G[cur.v][i].w > mid) res = 1;//如果第i条边的边权比二分过的答案大,则赋值为1 
            else res = 0;//否则赋值为0 
            if(dis[G[cur.v][i].v]>dis[cur.v]+res){//核心代码:从这个点衍生的点如果有更优的可能则更新为更优的方法 
                dis[G[cur.v][i].v]=dis[cur.v]+res;
                nxt.v=G[cur.v][i].v;//之后可用更新后的点继续更新其它点 
                nxt.w=dis[G[cur.v][i].v];
                save.push(nxt);
            }
        }
    }
    if(dis[n] <= k) return true;
    return false;
}


void binary(){
    int mid,l=0,r=1000000,ans=-1;
    //每次舍弃掉一半
    while(l<=r){//l~r代表我们当前答案可能在的区间为[l,r]
        mid=(l+r)/2;
        if(dij(mid)){//如果是真,即为大于枚举值的值大于k+1个
            r=mid-1;
            ans=mid;
        }else{
            l=mid+1;
        }
    }
    cout<<ans<<endl;
    return ;
}
int main(){
    cin>>n>>p>>k;
    int a,b,l;
    node tmp;
    for(int i=1;i<=p;i++){
        cin>>a>>b>>l;
        tmp.v=b;
        tmp.w=l;
        G[a].push_back(tmp);
        tmp.v=a;
        G[b].push_back(tmp);
    }
    binary();
    return 0;
}

本文链接:https://kaispace.com.cn/index.php/archives/448/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者