#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
#define ri register int
#define il inline
int n,m,ans;
int father[305];
struct road
{
int dis,from,to;
}
edge[200005];
il bool cmp(road a,road b)
{
return a.dis<b.dis;
}
il int find(int x)
{
if(father[x]!=x)father[x]=find(father[x]);
return father[x];
}
il void unionn(int x,int y)
{
father[find(x)]=find(y);
}
il void kruskal()
{
sort(edge+1,edge+m+1,cmp);
for(ri i=1;i<=m;i++)
{
if(i==n)
{
printf("%d %d",n-1,edge[i-1].dis);
return;
}
if(find(father[edge[i].from])!=find(father[edge[i].to]))
unionn(edge[i].from,edge[i].to);
}
}
il int read()
{
char c=getchar();int x=0,t=1;
while(c<'0'||c>'9'){if(c=='-')t=-1;c=getchar();}
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^'0'),c=getchar();
return t*x;
}
int main()
{
n=read();m=read();
for(ri i=1;i<=n;i++)father[i]=i;
for(ri i=1;i<=m;i++)
{
edge[i].from=read();
edge[i].to=read();
edge[i].dis=read();
}
kruskal();
return 0;
}
by BookofDeath @ 2019-02-07 23:05:46
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
#define ri register int
#define il inline
int n,m,ans;
int father[305];
struct road
{
int dis,from,to;
}
edge[200005];
il bool cmp(road a,road b)
{
return a.dis<b.dis;
}
il int find(int x)
{
if(father[x]!=x)father[x]=find(father[x]);
return father[x];
}
il void unionn(int x,int y)
{
father[find(x)]=find(y);
}
il void kruskal()
{
sort(edge+1,edge+m+1,cmp);
for(ri i=1; i<=m; i++)
{
if(i==n)
{
printf("%d %d",n-1,edge[i-1].dis);
return;
}
if(find(father[edge[i].from])!=find(father[edge[i].to])) unionn(edge[i].from,edge[i].to);
}
}
il int read()
{
char c=getchar();
int x=0,t=1;
while(c<'0'||c>'9')
{
if(c=='-')t=-1;
c=getchar();
}
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^'0'),c=getchar();
return t*x;
}
int main()
{
n=read();
m=read();
for(ri i=1; i<=n; i++)father[i]=i;
for(ri i=1; i<=m; i++)
{
edge[i].from=read();
edge[i].to=read();
edge[i].dis=read();
}
kruskal();
return 0;
}
```
by jijidawang @ 2020-02-02 13:24:38