洛谷P1948题解。

题目描述

多年以后，笨笨长大了，成为了电话线布置师。由于地震使得某市的电话线全部损坏，笨笨是负责接到震中市的负责人。该市周围分布着$N(1<=N<=1000)$根据$1……n$顺序编号的废弃的电话线杆，任意两根线杆之间没有电话线连接，一共有$p(1<=p<=10000)$对电话杆可以拉电话线。其他的由于地震使得无法连接。

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

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

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

题目分析

有一说一，不看题解我是万万想不到的，这得是多厉害猜想得到这题是用二分去解决的。不过如果能发现这题的答案的单调性，也许真的可以写出来。

首先第一点我想的肯定就是最短路啦，但是本题目求的并不是最短路，仔细看，如果路线个数少于 $k$ 个，则0元购，否则将会取得所有路线的最长的一条路径作为费用。可以看到这个题目它并不具备无后效性，它属于有后效性，有后效性即前面做出的选择对之后的选择有影响，如果题目就是求总共的最短路那么它就是无后效性。因为我当前在一个点上的时候你不需要去管我怎么到的这，因为就一个最短路径的值在这里，不管你前面怎么走的这个值是不会影响后面的结果的。

那么这是一个有后效性的题目那怎么办呢，答案是二分。

二分的判断条件就是，在我预算为mid的时候能否成功建成，很容易可以找到规律，如果mid能建成，那么>mid的情况一定能建成，如果mid不能建成，那么<mid的情况一定也不能建成，以此作为二分的依据。我们跑最短路的时候只需要检测路线上有多少个超过mid的边即可，如果超过k，说明预算一定超过mid，如果没到，说明预算太多了，大于mid的答案就都排除了，然后每次二分跑一次单源最短路。在 $n=1000$ 的情况下复杂度完全允许。

就是说，还得多练习，不然完全想不到能用这样的方法去做。

标程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<bits/stdc++.h>
#define maxn 5005
#define INF 0x3f3f3f3f
using namespace std;
typedef pair<int,int> P;
struct eee{
    int next;
    int to;
    int w;
}edge[maxn*maxn*2];
 int n,m,k,cnt,root[maxn],d[maxn],vis[maxn];
 priority_queue<P,vector<P>,greater<P>>s;
void add(int x,int y,int w){
    edge[++cnt].next=root[x];
    edge[cnt].w=w;
    edge[cnt].to=y;
    root[x]=cnt;
    return ;
}
int bfs(int x){
    memset(d,0x3f,sizeof(d));
    //memset(vis,0,sizeof(vis));
    d[1]=0;
    //vis[1]=1;
    s.push({0,1});
    while(!s.empty()){
        auto p=s.top();
        s.pop();
        int point=p.second;
        if(d[point]<p.first)continue;
        for(int i=root[point];i;i=edge[i].next){
            int to=edge[i].to;
            if(vis[to])continue;
            //vis[to]=1;
            if(d[to]>d[point]+(edge[i].w>x?1:0)){
                //vis[to]=1;
                d[to]=d[point]+(edge[i].w>x?1:0);
                s.push({d[to],to});
            }
        }
    }
    //printf("mid=%d:d[n]=%d\n",x,d[n]);
//    for(int i=1;i<=n;i++){
//        printf("%d ",d[i]);
//    }
    //putchar(10);
    if(d[n]==INF)return -1;
    if(d[n]>k)return 1;
    else return 0;
}
int main(){
    //freopen("P1948_2.in","r",stdin);
    ios::sync_with_stdio(false);
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
        int x,y,w;
        cin>>x>>y>>w;
        add(x,y,w);
        add(y,x,w);
    }
    
    int l=1,r=1000000,ans=-1;
    while(l<=r){
        int mid = l+r>>1;
        int value=bfs(mid);
        if(value==-1){
            printf("-1\n");
            return 0; 
        }
        if(value==1){
            l=mid+1;
        }
        else{
            r=mid-1;
            ans=mid;
        }
    }
    printf("%d\n",ans);
    
    return 0;
}