洛谷题单指南-最小生成树-P1396 营救

原题链接：https://www.luogu.com.cn/problem/P1396

题意解读：找到一条从s到t的路径，使得最大边权值最小，求这个最大的边权值。

解题思路：

根据kruskal的算法模型，对边权值小到大处理的过程，如果加入某条边权后，出现s、t连通，那么最后一次的边权即s到t路径上的最大边权最小值。

证明：如果存在s到t路径上更小的最大边权，那么这样的生成树的权值比kruskal算法生成树的权值更小，而kruskal算法生成的树就是最小生成树，产生矛盾。

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 10004, M = 20005;
struct Edge
{
    int u, v, w;
} edges[M];
int p[N];
int n, m, s, t;

bool cmp(Edge a, Edge b)
{
    return a.w < b.w;
}

int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int kruskal()
{
    sort(edges + 1, edges + m + 1, cmp);
    for(int i = 1; i <= n; i++) p[i] = i;
    for(int i = 1; i <= m; i++)
    {
        int a = find(edges[i].u);
        int b = find(edges[i].v);
        if(a != b)
        {
            p[a] = b;
            if(find(s) == find(t)) return edges[i].w;
        }
    }
}

int main()
{
    cin >> n >> m >> s >> t;
    for(int i = 1; i <= m; i++) 
    {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    }
    cout << kruskal();
    return 0;
}