1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
|
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=15100;
struct {
int from,to,cost;
}es[maxn],ans[maxn];
bool cmp(const edge &a,const edge &b)
{
return a.cost<b.cost;
}
int pre[maxn],rk1[maxn];
int n,m;
void init()
{
for(int i=0;i<=n;i++)
{
pre[i]=i,rk1[i]=0;
}
}
int find(int x)
{
if(pre[x]==x)
return x;
return pre[x]=find(pre[x]);
}
void unite(int x,int y)
{
x=find(x);
y=find(y);
if(x==y)
return;
if(rk1[x]<rk1[y])
pre[x]=y;
else
{
pre[y]=x;
if(rk1[x]==rk1[y])
rk1[x]++;
}
}
void kruskal()
{
int cnt=0;
sort(es,es+m,cmp);
init();
int res=0;
for(int i=0;i<m;i++)
{
edge e=es[i];
if(find(e.from)!=find(e.to))
{
unite(e.from,e.to);
ans[cnt].from=e.from;
ans[cnt++].to=e.to;
res=max(e.cost,res);
}
}
printf("%dn%dn",res,cnt);
for (int i=0;i<cnt;i++)
{
printf("%d %dn",ans[i].from,ans[i].to);
}
}
int main()
{
while (~scanf("%d%d",&n,&m))
{
for (int i=0;i<m;i++)
{
scanf("%d%d%d",&es[i].from,&es[i].to,&es[i].cost);
}
kruskal();
}
}
|
近期评论