Luogu P1948 [USACO08JAN]电话线

这是一个我认为思路比较奇妙的图论题

题目链接

  • 看到这道题的时候,我并没有想到二分,然后看了题解才发现好像确实是可以二分的,因为是要求整条路径上最大的边权最小,所以二分边权(即答案)。
  • 对于每一条边,如果它的边权大于mid,说明它需要用掉一个把该边设置为0的权力,因此边权为1,而一个边权小于mid时,其不需要用掉把边权变成0的权利,因为它本身就不是那个“最大的”边权。
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
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;

int n, m, k;
struct Edge{
int to, nxt, w;
}e[20009];
int head[1009], tot;
bool vis[1009];
int d[1009];

void add(int x, int y, int w){
e[++tot].to = y;
e[tot].w = w;
e[tot].nxt = head[x];
head[x] = tot;
}

bool dijkstra(int s, int limit){
priority_queue<pair<int, int> > pq;
memset(vis, 0, sizeof(vis));
memset(d, 0x3f3f3f3f, sizeof(d));
d[s] = 0;
pq.push(make_pair(-d[s], s));
while(!pq.empty()){
int x = pq.top().second;
pq.pop();
vis[x] = 1;
for(int i = head[x]; i; i = e[i].nxt){
int y = e[i].to, w = e[i].w;
if(w > limit) w = 1;
else w = 0;
if(d[y] > d[x] + w){
d[y] = d[x] + w;
pq.push(make_pair(-d[y], y));
}
}
}
if(d[n] > k) return false;
else return true;
}

int main(){
scanf("%d%d%d", &n, &m, &k);
for(int i = 1; i <= m; i++){
int x, y, w;
scanf("%d%d%d", &x, &y, &w);
add(x, y, w);
add(y, x, w);
}
int l = 0, r = 1000009;
while(l < r){
int mid = (l + r) / 2;
if(dijkstra(1, mid)) r = mid;
else l = mid + 1;
}
if(l > 1000000) printf("-1\n");
else printf("%d\n", l);
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×