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

· · 题解

其实吧，个人认为这个题作为一个蓝题是被评高了

核心算法：单源最短路 + 二分答案

(我为什么说评高了:

单源最短路（弱化版）：洛谷难度评级：普及/提高-（这题并没有卡SPFA）

标准的二分答案题：【P1182 数列分段Section II】 与【P1316 丢瓶盖】 ：洛谷难度评级：普及/提高-

两个黄题合在一起居然蓝了....

不说这个难度，开始讲题。

首先仍然是分析题意。

核心条件：

  1. 一开始在1号节点，要到达终点n号节点

  2. 每个点会有一个费用

  3. 每条道路都有一个对应的损失血量

次要条件（同样重要）

  1. 道路为双向

  2. 只有血量会使他无法到达终点（土豪不会被钱卡住）

题目目的：

求出到达路线中最大收费的最小值

把这些要点提炼出来后，就差不多可以开始写题了。

首先，看见这个问题，就应该想到二分。

所有类似于“求解所有的最大值中的最小值”的问题，都应该先想一想用二分答案的方法来写。

为什么呢？因为二分答案就是用来求解这种问题的，它通过猜测目前的答案+验证目前答案是否成立来求解，这种“假设已经知道答案”的方法比用题目信息求解答案的方法要优秀很多，而且复杂度也仅仅是加了一个log。

但是还要注意一点，除了这种经典问法以外，还要通过答案是否具有单调性来判断是否可以使用二分答案的方法

不具有单调性的问题是不可以使用这种方法的！

回到本题，我们猜测可以使用二分答案后，再验证：由于“我们假设需要的钱”越多，能走的点也就越多，可以走到终点的可能性也就越大，所以，这题是完全可以通过二分答案来写的。

然后，我们发现这里有两个变量：血量和费用。至于费用，我们已经用二分答案解决了，现在只需要解决血量的问题。 我们在上面分析了，损失血量是和边绑定在一起的，所有可以把损失血量看做每条边的长度，进而就到了这题的中心——单源最短路。

单源最短路径就不多说了，这题没有卡spfa，所以想怎么求就可以怎么求。因为我是把堆优化的dijkstra算法完完整整的理解性背了下来，所以直接套的dijkstra。虽然速度可能没有spfa那么快，但不会被卡啊。（我会跟你说我完全不会spfa吗

然后就是具体实现了。

（仍然分开给出）:

标准二分模板：

    int l=1,r=MAXN,mid=(l+r)>>1;//准备开始二分
    int c;
    while(l<=r){//终止条件
        c=work(mid);//使用work函数来判断当前猜测的答案是否可行
        if(c){//如果可以的话 
            r=mid-1;//改变右端点，看看再少一点是不是也可以
            mid=(l+r)>>1;
         }
        else{
            l=mid+1;//当前答案不可行，需要增大答案
            mid=(l+r)>>1;
         }
     }
     cout<<l<<endl;//输出找到的答案
}

然后是最短路....

说实话，如果你不习惯用“前向星＋小根堆＋pair”的话，很可能看不懂我写的什么玩意..建议使用自己熟悉的算法。

说一下最核心的改变，原版最短路为：

    while(q.size()!=0){
        s1=q.top().second;q.pop();
        if(ed[s1])continue;
        ed[s1]=1;
        s2=head[s1];
        while(s2){
                if(d[edge[s2].to]>d[s1]+edge[s2].dis&&ed[edge[s2].to]==0){
                d[edge[s2].to]=d[s1]+edge[s2].dis;
                q.push(make_pair( d[edge[s2].to] , edge[s2].to));
             }
             s2=edge[s2].next;
         }
    }

更改一个很小的细节：

while(que.size()){
        s1=que.top().second;que.pop();
        if(ed[s1])continue;
        ed[s1]=1;
        s2=head[s1];
        while(s2){//只有收费小于x的才能使用，大于x的一律视为没有 
//***************增加一个判定条件************************************************
            if(f[e[s2].to]<=x&&ed[e[s2].to]==0&&dis[s1]+e[s2].len<dis[e[s2].to])
            {dis[e[s2].to]=dis[s1]+e[s2].len;
            que.push(make_pair(dis[e[s2].to],e[s2].to));
            }//入堆准备下一轮操作 
            s2=e[s2].next;//去下一条边 
        }
    }

每次枚举答案时把只在符合当前答案的点里面找最短路，然后判断是否成立。

因为我这里是直接套用P4779 【模板】单源最短路径（标准版）的代码，所以代码看上去可能又烦又长...但最总要的是解题思路，如果你能想到使用二分答案并修改求最短路条件的话，两个基本上就是套模板的代码就很好写了。

放上我自己写的AC代码，可以用来参考一下细节（虽然对不会前向星或者堆优化的萌新来说可能不太友好，但我真的没用过spfa或者原版dijkstra...抱歉了）

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue> 
#include<cstring>
#define il inline
#define rg register
#define N 10005
#define M 100005
#define MAXN 1000000005//最大收费（二分用 
using namespace std;
int f[N];//每个城市的收费额度
bool ed[N];//求最短路使用
int dis[N];//同上
int head[N];//前向星 
priority_queue <pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > que;
int n,m,b;
int t;
struct edge{
    int to,next,len;
}e[M];
il void add(int x,int y,int z){
    e[++t].len=z;
    e[t].to=y;
    e[t].next=head[x];
    head[x]=t;
}
il int read(){
    int sum=0;char a=getchar();
    while(a<'0'||a>'9')a=getchar();
    while(a>='0'&&a<='9'){
        sum=(sum<<3)+(sum<<1)+a-'0';
        a=getchar();
    }
    return sum;
}
il bool work(int x){//对于每个最大收费都确定是否可以到达 
   if(x<f[1])return 0;//起点都过不了走个p 
    for(int i=1;i<=n;i++){
        dis[i]=1e9;//初始化为极大值 
    }
    memset(ed,0,sizeof(ed));
    dis[1]=0;
    que.push(make_pair(0,1));
    int s1,s2;
    while(que.size()){
        s1=que.top().second;que.pop();
        if(ed[s1])continue;
        ed[s1]=1;
        s2=head[s1];
        while(s2){//只有收费小于x的才能使用，大于x的一律视为没有 
            if(f[e[s2].to]<=x&&ed[e[s2].to]==0&&dis[s1]+e[s2].len<dis[e[s2].to])
            {dis[e[s2].to]=dis[s1]+e[s2].len;
            que.push(make_pair(dis[e[s2].to],e[s2].to));}//入堆准备下一轮操作 
            s2=e[s2].next;//去下一条边 
        }
    }
    if(dis[n]<b){
        return 1;
    }
    return 0;
}
int main(){
    n=read();m=read();b=read();
    for(rg int i=1;i<=n;i++)
    f[i]=read();//储存费用
    int a1,a2,a3;
    for(rg int i=1;i<=m;i++){
        a1=read();a2=read();a3=read();
        add(a1,a2,a3);
        add(a2,a1,a3);
    }
    if(work(MAXN)==0){
        cout<<"AFK"<<endl;
        return 0;//如果所有都开通任然不满足条件，剩下的肯定也不会满足 
    } 
    int l=1,r=MAXN,mid=(l+r)>>1;//准备开始二分
    int c;
    while(l<=r){
        c=work(mid);
        if(c){//如果可以的话 
            r=mid-1;
            mid=(l+r)>>1;
         }
        else{
            l=mid+1;
            mid=(l+r)>>1;
         }
     }
     cout<<l<<endl;
}

还有什么不理解的可以回复并@我，只要我看见了就会回复的。