题解 P1396 【营救】

· · 题解

令人智熄的二分操作

AC记录

要看正常的解法请看其他题解

而且还蛮快的。。。

其实，这是非常奇葩的一个想法

总体思路就是：二分答案

你没听错，二分答案

我们从题面中可以看到，其实这道题的拥挤度也就10000而已，所以我们就会发现二分似乎可以？？？

存图存完之后直接二分，二分的Check()里面打一个BFS，来求能否通往终点，就好了

具体的东西就上代码来看吧

#include<bits/stdc++.h> // 万能头文件 

using namespace std;

// 邻接表存图 
// 由于是无向图，所以这些数组要开大一倍，我就是这么被坑掉了10分 
int End[50100]; // End[i]表示第i条边的终点 
int Value[50100]; // Value[i]表示第i条边的边权 
int Next[50100]; // Next[i]表示第i条边的下一条边 
int Head[10100]; // Head[i]表示第i个点的第一条便

int q[50100]; // BFS的队列 
int n, m, s, t; // 如题意 
int qf, qe; // BFS队列的队首、队尾 
bool Used[10100]; // BFS，表示是否到过这个点 

bool Check(int x){
    memset(Used, false, sizeof(Used)); // 朴实无华的BFS 
    qf = qe = 1;
    q[1] = s;
    Used[s] = true;
    while(qf <= qe){
        int xx = Head[q[qf]];
        while(xx != -1){
            if(!Used[End[xx]] && Value[xx] <= x){ // 拓展 
                q[++qe] = End[xx];
                Used[End[xx]] = true;
            }
            xx = Next[xx]; 
        }
        qf++; // 出队 
    }
    return Used[t]; // 返回终点有没有到过 
}

int main(){
    memset(Next, -1, sizeof(Next));
    memset(Head, -1, sizeof(Head));
    scanf("%d %d %d %d", &n, &m, &s, &t);
    int r = 0;
    for(int i = 1; i <= m; i++){ // 读入、存图 
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        Value[i*2] = c;
        End[i*2] = b;
        Next[i*2] = Head[a];
        Head[a] = i*2;
        Value[i*2+1] = c; // 由于是无向图，所以要存两次 
        End[i*2+1] = a;
        Next[i*2+1] = Head[b];
        Head[b] = i*2+1;
        if(c > r)
            r = c; // 生成一个值等于所有最高拥挤度的r，方便二分 
    }
    // ------------读入完毕---------------
    // ------------二分开始--------------- 
    r++;
    int l = 1;
    while(l < r){ // 同样朴素的二分~~~ 
        int Mid = ((l+r) >> 1);
        if(Check(Mid))
            r = Mid;
        else l = Mid+1;
    }
    printf("%d", l);
}

感谢 学委 对我的启发