这题弄k各部落
就是把它合并成k个集合
所以按最小的边合并的解一定是最优的
这就借用了k算法的思想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#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
struct bbb{
int x,y;
int s;
};
bbb p[1000000+100];
int f[1999],s[1999];
int find(int x)
{
if(f[x]==x) return x;
return f[x]=find(f[x]);
}
int cmp(const bbb a,const bbb b)
{
if(a.s<b.s)
return 1;
return 0;
}
int t,ans;
int n,m,k;
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=m;i++)
scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].s);
for(int i=1;i<=n;i++)
f[i]=i;
sort(p+1,p+m+1,cmp);
for(int i=1;i<=n-k;i++)
{
int fx=1,fy=1;
while(fx==fy){
++t;
if(t>m) {
printf("No Answer");
return 0;
}
fx=find(p[t].x),fy=find(p[t].y);
}
f[fx]=fy;
ans+=p[t].s;
}
printf("%d",ans);
}
