最小生成树,所有连通边的最大值
我唯一想说的是:我卢本伟没有开挂 ,第二句话是个废话,让一个树连通,边的数量是定制n-1(n为点数)。
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<queue>
#include<set>
#define IL inline
#define x first
#define y second
typedef long long ll;
using namespace std;
const int N=2000010;
struct node{
int a;
int b;
int c;
bool operator <(const node&w) const
{
return c<w.c;
}
}q[N];
int n,m;
int p[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<=n;i++)
p[i]=i;
for(int i=0;i<m;i++)
{
int a,b,c;
cin>>a>>b>>c;
q[i].a=a;
q[i].b=b;
q[i].c=c;
}
sort(q,q+m);
int cnt=0;
int res=0;
for(int i=0;i<m;i++)
{
int a=q[i].a,b=q[i].b,c=q[i].c;
a=find(a),b=find(b);
if(a!=b)
{
p[a]=b;
cnt++;
res=max(res,c);
}
}
cout<<cnt<<' ';
cout<<res<<endl;
return 0;
}