题解 P1462 【通往奥格瑞玛的道路】

P1462 题解


题目大意:

给定一个$n$个点的无向图,求在满足从$1$到$n$的最短路边权和 $\leq b$ 的情况下,所经过的点的最大点权的最小值。

思路:

带有 “最大值最小” 的“双最”字样的最优化题目一般比较难直接求解,这时候我们不妨用二分的思想,将最优化问题转换为判断合法性问题。

二分代码模板:

1
2
3
4
5
6
7
while(l<=r)
{
mid=(l+r)>>1;
if(check(mid)) ans=mid,r=mid-1; //如果解合法,记录答案并缩小左边界
else l=mid+1;//否则缩小右边界
}
cout<<ans<<endl;

check()函数的设计:

首先,假设我们已经找到了一个解 $val$,那么所有点权 $> val$的点就不能被访问了(因为如果这样做就不满足解)。然后再求出$1$到$n$的最短路 (SPFAer和Dijkstrer们可以不要争了,这个优先队列BFS就可以做,还比你们都快 233),之后判断最短路的权值和是否 $\leq b$ ,如果不满足则说明解不合法 (会被揍死)

一些小坑点:

  • 二分时需要判断 “无论如何也无法到达的情况”
  • fi≤1000000000,因此直接二分会T飞,要先离散化;
  • ci≤1000000000,记得开 long long 不然炸飞;

代码:

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<cstring>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;
const int maxn=10005;
typedef long long ll;
int n,m,b;

inline ll read()//快读
{
ll s=0,w=1;
char c=getchar();
while(c<'0' || c>'9'){
if(c=='-') w=-1;
c=getchar();
}
while (c>='0' && c<='9') {
s=(s<<3)+(s<<1)+(c^48);
c=getchar();
}
return s*w;
}

/**
* BFS的记录结构体
* @param cur 当前点
* @param c 已经扣掉的血量
*/
struct note{
ll cur,c;
note(ll a,ll b):cur(a),c(b) {}
note() {}
};
//没什么好说的,比较运算符
struct cmp{
bool operator () (note a,note b)
{
return a.c>b.c;
}
};
//pbds的黑科技堆,详细描述可以看这里:https://blog.xehoth.cc/pb-ds-PriorityQueue/
typedef __gnu_pbds::priority_queue<note,cmp,__gnu_pbds::pairing_heap_tag> heap;

//vector数组存图
struct edge{
ll to;ll w;
edge(ll a,ll b):to(a),w(b) {}
edge() {}
};
vector<edge> e[maxn];
ll v[maxn];//点权数组
/**
* 增加一条x到y,权值为w的边
*/
inline void addedge(ll x,ll y,ll w)
{
e[x].push_back(edge(y,w));
}

//BFS部分
bool vis[maxn];
ll bfs(ll val)
{
memset(vis,0,sizeof(vis));
heap q;
q.push(note(1,0));
vis[1]=true;
while(!q.empty())
{
note cu=q.top();
q.pop();
if(cu.cur==n){
return cu.c;
}
ll& st=cu.cur;
ll& co=cu.c;
for(int i=0;i<e[st].size();i++)
{
ll& to=e[st][i].to;
if(!vis[to] && v[to]<=val)
{
q.push(note(to,co+e[st][i].w));
vis[to]=true;
}
}
}
return 0x3f3f3f3f;//如果到不了返回无穷大
}

ll lsv[maxn];//离散数组
int main()
{
n=read(),m=read(),b=read();
for(int i=1;i<=n;i++) lsv[i-1]=v[i]=read();
for(int i=1,x,y,w;i<=m;i++) {
x=read(),y=read(),w=read();
if(x!=y) addedge(x,y,w),addedge(y,x,w);
}
//离散化
sort(lsv,lsv+n);
int sz=unique(lsv,lsv+n)-lsv;
//二分
int l=0,r=sz,mid,ans=-1;
while(l<=r)
{
mid=(l+r)>>1;
if(bfs(lsv[mid])<=b) ans=mid,r=mid-1;
else l=mid+1;
}
if(ans==-1){//如果答案没被更新过即为“不可到达”
printf("AFK\n");
return 0;
}
else printf("%lld\n",lsv[ans]);//输出答案
}

总时间复杂度:$O(nlogn * logn) = O(nlog^2 n)$,比几乎所有题解都要快

文章作者: 1379号监听员
文章链接: https://listener1379.site/2019/题解-P1462-【通往奥格瑞玛的道路】/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 1379号监听站
支付宝打赏
微信打赏