URAL 2034 Caravans(最短路 + 二分)

题目大意

给出 $n$ 个点,$m$ 条边的无向带权图(权值都为1),镖车将从起点 $s$ 出发到达终点 $f$,保证走最短路径。强盗在点 $r$ 处,他想通过预先埋伏的方式拦截镖车(甚至可以在 $s$ 或者 $f$ 埋伏)。并且强盗希望在离 $r$ 最近的点埋伏,问最坏情况下需要走的最远距离。
$( 3 \leq n \leq 10^5, 2 \leq m \leq 10^5)$

解题思路

最短路 + 二分

题意有点难理解,特别是这部分:

Among all such settlements the robbers will choose the one closest to settlement r.
They don’t know the caravan’s route yet, but they want to know the maximum distance they will have to go in the worst case to the settlement where they will rob the caravan.

一开始理解为必须保证拦截,所以思路就是求 $s$ 到 $f$ 最短路径图的割点中离 $r$ 距离最短的点。可是又无法解释 “maximum distance”。后来才发现应该是求 $r$ 到最短路(可能不止一条)最近距离的最大值。

最大化最小值。很容易联想到二分。先跑出 $r$ 到各个点的最短距离 $d_i$,然后直接二分答案(距离),每次将小于距离的 $d_i$ 对应的点删除,然后跑 $s$ 到 $f$ 的最短路,看是否满足到 $f$ 的距离最短就可以了。

代码如下:
(注意二分的写法:距离越小越满足,越大越不满足,求最大)

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>

using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 10;
const int MAXM = 1e5 + 10;

struct edge {
int to, next;
edge( int to = 0, int next = 0 ) : to(to), next(next) {}
} G[MAXM << 1];
int n, m;
int tot, head[MAXN];
int d[MAXN], vis[MAXN], D[MAXN];
int s, f, r;
int ans;

void add_edge(int u, int v)
{

G[tot] = edge(v, head[u]);
head[u] = tot++;
G[tot] = edge(u, head[v]);
head[v] = tot++;
}
void init()
{

tot = 0;
memset(head, -1, sizeof(head));
memset(vis, 0, sizeof(vis));
}
void bfs(int ss)
{

memset(d, -1, sizeof(d));
if( vis[s] ) return ;
queue<int> que;
que.push(ss);
d[ss] = 0;
vis[ss] = true;
while( !que.empty() )
{
int u = que.front(); que.pop();
for( int i = head[u]; ~i; i = G[i].next )
{
int v = G[i].to;
if( !vis[v] && d[v] == -1 )
{
d[v] = d[u] + 1;
vis[v] = true;
que.push(v);
}
}
}
}
int main()
{

while( ~scanf("%d %d", &n, &m) )
{
init();
int u, v;
for( int i = 0; i < m; ++ i )
{
scanf("%d %d", &u, &v);
add_edge(u, v);
}
scanf("%d %d %d", &s, &f, &r);
bfs(s);
ans = d[f];
memset(vis, 0, sizeof(vis));
bfs(r);
for( int i = 1; i <= n; ++ i ) D[i] = d[i];
int L = -1, R = 0;
for( int i = 1; i <= n; ++ i )
{
R = max(R, D[i]);
}
while( R - L > 1 )
{
int m = (L + R) >> 1;
memset(vis, 0, sizeof(vis));
for( int i = 1; i <= n; ++ i )
{
if( D[i] <= m ) vis[i] = true;
}
bfs(s);
if( d[f] == -1 || d[f] > ans ) R = m;
else L = m;
}
printf("%d\n", R);
}
return 0;
}


另一种方法

从起点 $s$ 点出发,顺着到 $f$ 点的最短路径图,更新各路径到 $r$ 的最短距离,和各点所属路径中当前与 $r$ 的最大距离,一直跑到终点 $f$处。

如果您觉得这篇博文对您有所帮助,可以考虑请我吃颗糖哦!