题目链接

<h1>题目大意</h1>

给定一个图，求瓶颈最短路（及求出一条是该路径最大值最小的路径）。

<h1>解题报告</h1>

<h2>方法一</h2>

注意最大值最小，我们立马想到了二分。

实际上，由于这道题拥挤度的范围不大，可以二分。

二分的区间就在边权最小值与最大值之间。

我们使用bfs来检查答案。每次 bfs 时验证只通过边权不超过的值来判断答案是否可行。

具体代码如下。

#include <iostream>
#include <cstring>
#include <climits>
#include <cstdio>
#include <queue>

#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 10000 + 5;
const int MAXM = 2 * MAXN + 5;

int N,M,S,T;


struct Node{
    struct Edge *firstEdge;
    bool vis;
}node[MAXN];

struct Edge{
    Node s,t;
    int w;
    Edge *next;
}pool[MAXM  2],frog = pool;

Edge New(Node s,Node *t,int w){
    Edge *ret = ++frog;
    ret->s = s;ret->t = t;
    ret->w = w;ret->next = s->firstEdge;
    return ret;
}

inline void add(int u,int v,int w){
    node[u].firstEdge = New(&node[u],&node[v],w);
    node[v].firstEdge = New(&node[v],&node[u],w);
}

bool check(int k){
    for(int i = 1;i <= N;i++) node[i].vis = false;
    std::queue<Node *> q;
    q.push(&node[S]);
    while(!q.empty()){
        Node *v = q.front();
        q.pop();
        v->vis = true;
        for(Edge *e = v->firstEdge;e;e = e->next){
            if(!e->t->vis && e->w <=k){
                q.push(e->t);
                if(e->t == &node[T]) return true;
            }
        }
    }
    return false;
}

int main(){
    int L = INT_MAX,R = INT_MIN;
    scanf("%d%d%d%d",&N,&M,&S,&T);
    for(int u,v,w,i = 1;i <= M;i++){
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        L = std::min(L,w);
        R = std::max(R,w);
    }
    while(L < R){
        int mid = (L + R) >> 1;
        if(check(mid)) R = mid;
        else L = mid + 1;
    }
    printf("%dn",L);
    return 0;
}

<h2>方法二</h2>

我们可以借助于最小生成树的思想，每次我们判断一条边的两个点是否在同一集合，如果不在就合并。

对边进行排序。只需要整体扫一遍。

具体代码如下。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

const int MAXN = 10000 + 5;
const int MAXM = MAXN * 2 + 5;

int N,M,S,T;
int ans;

struct Edge{
    int u,v,w;
    
    bool operator < (const Edge &other) const{
        return w < other.w;
    }
}e[MAXM];

int f[MAXN];

int find(int x){
    return x == f[x] ? x : f[x] = find(f[x]);
}

void Kruskal(){
    int cnt = 0;
    for(int i = 1;i <= M;i++){
        int fu = find(e[i].u),fv = find(e[i].v);
        if(fu == fv) continue;
        ++cnt;
        if(find(S) == find(T)) break;
        //ans = std::max(ans,e[i].w);
        ans = e[i].w;
        f[fv] = fu;
        if(cnt == N - 1) break;
    }
}

int main(){
    scanf("%d%d%d%d",&N,&M,&S,&T);
    for(int i = 1;i <= N;i++) f[i] = i;
    for(int i = 1;i <= M;i++)
        scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
    std::sort(e + 1,e + M + 1);
    Kruskal();
    printf("%d",ans);
    return 0;
}