先说结论：最大边权最小的生成树=最小生成树

我的思路是，从小到大枚举可能的最小最大边，如果在最大值不超过该边的条件下做kruscal，cnt==n-1的话，则找到该边

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

using namespace std;

const int N=310,M=8100;         

int p[M];
int n,m;


struct Edge
{
    int a,b,w;

     bool operator< (const Edge &W)const
    {
        return w < W.w;
    }
}edge[M];


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

int kru(int len)
{
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        p[i]=i;

    }
    for(int i=1;i<=m;i++)
    {
        int a=edge[i].a;
        int b=edge[i].b;
        int w=edge[i].w;

        a=find(a);
        b=find(b);
        if(a!=b && w<=len)
        {
            p[a]=b;
            cnt++;
        }
    }
     if(cnt==n-1) return 1;
     else return -1;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        edge[i]={a,b,c};
    }
    sort(edge+1,edge+m+1);
    //int start_len=edge[n-1].w;
    for(int i=n-1;i<=m;i++)
    {
        int max_len=edge[i].w;
        int t=kru(max_len);
        if(t==1)
        {
            cout<<n-1<<" "<<max_len;
            break;
        }

    }

    //cout<<max_len;
    return 0;
}

y总的做法，太强了，直接kruscal，res保留最后一条插入集合的边的值，就是最小的最大值

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

using namespace std;

const int N=310,M=8100;         

int p[M];
int n,m;


struct Edge
{
    int a,b,w;

     bool operator< (const Edge &W)const
    {
        return w < W.w;
    }
}edge[M];


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


int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        edge[i]={a,b,c};
    }
    sort(edge+1,edge+m+1);
    //int start_len=edge[n-1].w;
    for(int i=1;i<=n;i++)
    {
        p[i]=i;

    }
    int res;
    for(int i=1;i<=m;i++)
    {
        int a=edge[i].a;
        int b=edge[i].b;
        int w=edge[i].w;

        a=find(a);
        b=find(b);
        if(a!=b)
        {
            p[a]=b;
            res=w;
        }
    }
    cout<<n-1<<" "<<res;
    return 0;
}

三刷，觉得自己一刷时的做法好傻，直接kruscal，最后一条边就是最小的最大值

根据kruscal的性质，选的边从小到大

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

using namespace std;

const int N=100010;
int n,m,p[N];

struct edge
{
    int a,b,w;
    bool operator< (const edge & W) const
    {
        return w<W.w;
    }
}edges[N];

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



int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        edges[i]={a,b,c};
    }

    sort(edges+1,edges+m+1);
    for(int i=1;i<=n;i++)
    {
        p[i]=i;
    }

    int res=0;
    int max_w;
    for(int i=1;i<=m;i++)
    {
        int a=edges[i].a;
        int b=edges[i].b;
        int w=edges[i].w;

        a=find(a);
        b=find(b);
        if(a!=b)
        {
            p[b]=a;
            res++;
            max_w=w;
        }
    }

    cout<<res<<" "<<max_w;

    return 0;
}

2023/12/22

kruscal模板题
这个题应该是利用kruscal的性质做的：
1. 因为是按边升序来找的，因此找到的最小生成树边数一定最少
2. 因为是按边升序来找的，因此最小生成树中最大的边权 一定是最小的

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const int N=10010;
int n,m;
int p[N];
// 记录每个集合内点的数量
int cnt[N];

struct Edge{
    int a,b,w;
    bool operator < (const Edge &W) const
    {
        return w<W.w;
    }
}edges[N];

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

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        p[i] = i;
        cnt[i] = 1;
    }

    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        edges[i].a = a;
        edges[i].b = b;
        edges[i].w = c;
    }

    sort(edges+1, edges+m+1);

    int max_w = 0;
    // 记录最小生成树边的数量
    int res = 0;
    for(int i=1;i<=m;i++)
    {
        int a = edges[i].a;
        int b = edges[i].b;
        int c = edges[i].w;

        a = find(a);
        b = find(b);

        if(a!=b)
        {
            p[a] = b;
            cnt[b] += cnt[a];
            max_w = max(max_w, c);
            res++;

            if(cnt[b] == n)
            {
                break;
            }
        }
    }

    cout<<res<<" "<<max_w;

    return 0;
}