标准的kruskal

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

贪心+并查集

从花费小的到大的依次合并。每一次合并不一定能够减少一个堆数。如果两个节点本来已经在一堆，那么这个合并就是不必要的。

Kruskal,合并n-k次而非标准的n-1次

[转化]最小生成森林问题（k颗树）。

[算法]我们用贪心+并查集的经典算法，稍加改进，在判边的时候记录已经合并过多少次集合，合并了n-k次以后即得到解。O(mlogm)。

若对该算法不了解，可参考最小生成树的相关资料。

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
struct node{
int x,y,z;
}gg[20005];
int fa[20005],cnt;
int find(int x)
{
if(x!=fa[x])return fa[x]=find(fa[x]);
return x;
}
int unionn(int x,int y)
{
int a=find(x),b=find(y);
fa[a]=b;
cnt++;
}
int cmp(const node &a,const node &b)
{
return a.z<b.z;
}
int main()
{
int n,m,k,ans=0;
cin>>n>>m>>k;
if(n==k)
{
cout<<"0";
return 0;
}
for(int i=1;i<=n;i++)
fa[i]=i;
for(int i=1;i<=m;i++)
cin>>gg[i].x>>gg[i].y>>gg[i].z;
sort(gg+1,1+gg+m,cmp);
for(int i=1;i<=m;i++)
{
if(cnt==n-k)break;
if(find(gg[i].x)!=find(gg[i].y))
{
unionn(gg[i].x,gg[i].y);
ans+=gg[i].z;
}
}
if(n-cnt!=k)
{
cout<<"No Answer";
return 0;
}
printf("%d",ans);
}

#include <cstdio>
#include <algorithm>

struct NODE{
int s1,s2,val;
}a[20000];

bool cmp(NODE a,NODE b){
return a.val<b.val;
}

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

int main(){
int n,m,k,sum=0,count=0;
freopen("in.txt","r",stdin);
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)
pre[i]=i;
for(int i=0;i<m;i++){
int s1,s2,val;
scanf("%d%d%d",&s1,&s2,&val);
a[i].s1=s1,a[i].s2=s2,a[i].val=val;
}
std::sort(a,a+m,cmp);
for(int i=0;i<m;i++){
if(count==n-k)
break;
int f1=find(a[i].s1);
int f2=find(a[i].s2);
if(f1==f2)
continue;
pre[f1]=f2;
sum+=a[i].val;
count++;
}
if(n-count!=k)
printf("No Answer");
else
printf("%d",sum);
return 0;
}

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int f[1005];
struct edge
{
    int from,to,len;
}road[80005];
bool comp(edge a,edge b){
    return a.len<b.len;
}
int getf(int x)
{
    return f[x]==x?x:f[x]=getf(f[x]);
}
int main()
{
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&road[i].from,&road[i].to,&road[i].len);
    sort(road+1,road+m+1,comp);
    int ans=0,j=n;
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<=m && j>k;i++) {
        int p1=getf(road[i].from);
        int p2=getf(road[i].to);
        if(p1!=p2) {
            ans+=road[i].len;
            f[p1]=p2;
            j--;
        }
    }
    j==k?printf("%d",ans):puts("No Answer");
    return 0;
}

kruskal模板水过，记得数组开大点