洛谷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;
}