修复公路 （最小生成树）

//新生训练

 Input

4 4
1 2 6
1 3 4
1 4 5
4 2 3

Output

5

#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
struct road
{
    int u,v;
    ll w;
    bool operator<(const road a)const{
        return w<a.w;
    }
};
 
 
const int MAXN=1005;
int f[MAXN];
int n,m;
ll ans=-1;
road r[100005];
 
int Find(int x)
{
    if(x==f[x]) return x;
    return f[x]=Find(f[x]);
}
 
void Merge(int x,int y)
{
    int a=Find(x);
    int b=Find(y);
    f[a]=b;
}
 
bool check()
{
    int fa=Find(1);
    for(int i=2;i<=n;++i)
    {
        if(fa!=Find(i)) return false;
    }
    return true;
}
 
int main()
{
    cin>>n>>m;
 
    for(int i=0;i<=n;++i)
    {
        f[i]=i;
    }
 
    for(int i=1;i<=m;++i)
    {
        cin>>r[i].u>>r[i].v>>r[i].w;
    }
 
    sort(r+1,r+m+1);
 
    for(int i=1;i<=m;++i)
    {
        Merge(r[i].u,r[i].v);
        if(check())
        {
            ans=r[i].w;
            break;
        }
    }
 
    cout<<ans;
 
    return 0;
}

 2024.04.17——学习最小生成树

现在暑假算是填坑吧 hwh

 ~~~仅当笔者个人备忘录使用。