并查集+prim（贪心）
得到K块连通分量要选择N-K条边，直接选最小的N-K条，要注意选的每条边两个端点不能已连通。
判断是否已连通可以用并查集实现。

#include <iostream>
#include <algorithm>

using namespace std;

typedef struct
{
    int a,b;
    int w;
}edge;

int n,m,k;
edge e[10000];
int f[1001];

int fi(int x)
{
    if(f[x]==x)
    {
        return x;
    }
    return f[x]=fi(f[x]);
}

void un(int a,int b)
{
    int x=fi(a);
    int y=fi(b);
    if(x!=y)
    {
        f[y]=x;
    }
}

bool comp(edge a,edge b)
{
    return a.w<b.w;
}

int main()
{
    cin>>n>>m>>k;
    if(m<n-k)
    {
        cout<<"No Answer"<<endl;
        return 0;
    }
    int i;
    for(i=0;i<=n;i++)
    {
        f[i]=i;
    }
    for(i=0;i<m;i++)
    {
        cin>>e[i].a>>e[i].b>>e[i].w;
    }
    sort(e,e+m,comp);
    int ans=0;
    int acc=n-k;
    for(i=0;i<m;i++)
    {
        if(fi(e[i].a)!=fi(e[i].b))
        {
            acc--;
            ans+=e[i].w;
            un(e[i].a,e[i].b);
            if(acc==0)
            {
                break;
            }
        }
    }
    if(acc==0)
    {
        cout<<ans<<endl;
    }
    else
    {
        cout<<"No Answer"<<endl;
    }
    return 0;
}

prim算法
求出n个云朵的最小生成树的代价，将它们连成一个棉花糖，然后选取最小生成树中代价最大的k-1个代价，将最小生成树的代价减去这k-1个代价即为花费最少。

轻松水过。。
var
n,m,i,j,k:longint;
selected:array[0..10000] of longint;
e:array[0..10000,1..2] of longint;
value:array[0..10000] of longint;
t:array[0..10000] of longint;
a:array[0..10000] of longint;
min,mine,valuet,g:longint;
procedure sort(l,r: longint);
var
i,j,x,y: longint;
begin
i:=l;
j:=r;
x:=a[(l+r) div 2];
repeat
while a[i]>x do
inc(i);
while x>a[j] do
dec(j);
if not(i>j) then
begin
y:=a[i];
a[i]:=a[j];
a[j]:=y;
inc(i);
j:=j-1;
end;
until i>j;
if l<j then
sort(l,j);
if i<r then
sort(i,r);
end;

begin
read(n,m,k);
for i:=1 to m do
readln(e[i,1],e[i,2],value[i]);
fillchar(selected,sizeof(selected),0);
fillchar(t,sizeof(t),0);
valuet:=0;
for i:=1 to n-1 do
begin
min:=maxlongint;
mine:=0;
for j:=1 to m do
if selected[j]=0 then
if ((t[e[j,1]]=0) xor (t[e[j,2]]=0)) or (i=1) then
if value[j]<min then
begin min:=value[j];mine:=j;end;
inc(g);
a[g]:=min;
selected[mine]:=1;
t[e[mine,1]]:=1;
t[e[mine,2]]:=1;
valuet:=valuet+min;
end;
sort(1,g);
for i:=1 to k-1 do
valuet:=valuet-a[i];
writeln(valuet);
end.

#include<bits/stdc++.h>
using namespace std;

int n,k,m,fa[1000050];
struct node {
    int x;
    int y;
    int l;
} a[1000005];

int cmp( const void *a , const void *b ) {
    struct node *c = (node *)a;
    struct node *d = (node *)b;
    return c->l - d->l;
}

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

void work(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x==y)
    return;
    fa[x]=y;
}

int main(){
    cin>>n>>m>>k;
    for(int i=0; i<m; i++)
        cin>>a[i].x>>a[i].y>>a[i].l;
    qsort(a,m,sizeof(a[0]),cmp);
    for(int i=1;i<=n;i++)
    fa[i]=i;
    int num=n-k;
    int ans=0;
    for(int i=0;i<m;i++)
    {
        if(num==0)
            break;
        int aaa=find(a[i].x);
        int wzx=find(a[i].y);
        if(aaa!=wzx)
        {
            work(a[i].x,a[i].y);
            ans+=a[i].l;
            num--;
        }
    }
    if(num)
        cout<<"No Answer";
    else
        cout<<ans;
    return 0;
}

#1 Accepted 2ms 700.0 KiB
#2 Accepted 2ms 616.0 KiB
#3 Accepted 1ms 232.0 KiB
#4 Accepted 5ms 356.0 KiB
#5 Accepted 4ms 372.0 KiB
#6 Accepted 5ms 348.0 KiB
#7 Accepted 4ms 348.0 KiB
#8 Accepted 4ms 348.0 KiB
#9 Accepted 4ms 360.0 KiB
#10 Accepted 4ms 352.0 KiB
//kruskal算法
#include <bits/stdc++.h>
using namespace std;
int f[1005],res,ans=0,n,m,k,x,y,l;
struct edge
{
int u,v,w;
}a[10005];
bool cmp(edge a,edge b)
{
return a.w<b.w;
}
int find(int x)
{
if(f[x]==x) return x;
else return f[x]=find(f[x]);

}
void kruskal()
{
for(int i=1;i<=n;i++) f[i]=i;
for(int i=1;i<=m;i++)
{
int u=find(a[i].u),v=find(a[i].v);
if(u!=v)
{
ans+=a[i].w; f[u]=v; res--;
}
if(res==k) return ;
}
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
res=n;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&l);
a[i].u=x; a[i].v=y; a[i].w=l;
}
sort(a+1,a+m+1,cmp);
kruskal();
if(res!=k) printf("No Answer");
else printf("%d",ans);
return 0;
}

MST后统计联通块个数然后从大到小删边

#include<bits/stdc++.h>
using namespace std;
const int N=10000+10,M=100000+10;
typedef long long ll;
int n,m,K,len,last[N],fa[N];
bool vis[N];
struct Edge
{
    int from,to,val;
    bool operator <(const Edge &rhs)const {
        return rhs.val>val;
    }
}e[M];
int find(int x){return fa[x]==x?fa[x]:fa[x]=find(fa[x]);}
void Kruskal()
{
    ll tot=0,ans=0,cnt=0;
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        int idx=find(e[i].from),idy=find(e[i].to);
        if(idx==idy)continue;
        ans+=e[i].val;
        fa[idx]=idy;
        vis[i]=1;
        cnt++;
    }
    int k=n-cnt;
    for(int i=m;i>=1&&k<K;i--)if(vis[i])tot+=e[i].val,k++;
    if(k<K)printf("No Answer\n"); 
    else printf("%lld\n",ans-tot);
}
int main()
{
    scanf("%d%d%d",&n,&m,&K);
    for(int u,v,w,i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        e[i].from=u;e[i].to=v;e[i].val=w;
    }
    sort(e+1,e+1+m);
    Kruskal();
    return 0;
}

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

struct edge_1
{
    int x,y,d;
};

int n,m,t,cnt,ans;
vector<int> fa;
vector<edge_1> e;

void c_v_1()
{
    fa.resize(0);
    e.resize(0);
}

bool cmp_edge_1(edge_1 x,edge_1 y)
{
    return x.d<y.d;
}

int find_fa_1(int x)
{
    return ((fa[x]==x)?x:(fa[x]=find_fa_1(fa[x])));
}

int unite_1(int x,int y)
{
    if (fa[(fa[y]=find_fa_1(fa[y]))]!=(fa[x]=find_fa_1(fa[x])))
    {
        fa[fa[y]]=fa[x];
        return 1;
    }
    else
        return 0;
}

int main()
{
    while (~scanf("%d%d%d",&n,&m,&t))
    {
        c_v_1();
        fa.resize(n+1,0);
        for (int i=1;i<=n;i++)
            fa[i]=i;
        e.resize(m+1);
        for (int i=1;i<=m;i++)
            scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].d);
        sort(e.begin()+1,e.end(),cmp_edge_1);
        cnt=ans=0;
        for (int i=1;i<=m&&cnt<n-t;i++)
        {
            int suc=unite_1(e[i].x,e[i].y);
            cnt+=suc;
            ans+=e[i].d*suc;
        }
        if (cnt>=n-t)
            printf("%d\n",ans);
        else
            printf("No Answer\n");
    }
}

因为共有n朵云并且一朵云就可以构成一个棉花糖，所以不用云构造花费为0，那么就要留出k-1朵云单独作为一个棉花糖，即将剩下的n-（k-1）朵云构造成一棵最小生成树，即当加入的边数=n-(k-1)-1时构造完成。此时构造的为最小生成树，构造这个棵树花费最小，其他花费为0，所以这样就以最小的花费构造出了k个棉花糖；
算法以并查集优化的kruscal来构造即可。

###代码如下

program p1234;
type rec=record
s,e,v:longint;
end;
var i,j,n,m,k,cost:longint;
father:array[1..1000] of longint;
map:array[1..10000] of rec;
procedure qsort(i,j:longint);
var l,r,mid:longint;
temp:rec;
begin
l:=i;
r:=j;
mid:=map[(l+r)>>1].v;
while l<=r do
begin
while map[l].v<mid do inc(l);
while map[r].v>mid do dec(r);
if l<=r
then
begin
temp:=map[l];
map[l]:=map[r];
map[r]:=temp;
inc(l);
dec(r);
end;
end;
if l<j then qsort(l,j);
if i<r then qsort(i,r);
end;

function find(x:longint):longint;
begin
if father[x]=x then exit(x);
father[x]:=find(father[x]);
exit(father[x]);
end;

procedure unite(a,b:longint);
begin
father[find(father[a])]:=find(father[b]);
end;

begin
readln(n,m,k);
if n<k then
begin
write('No Answer');
exit;
end;
for i:=1 to m do
readln(map[i].s,map[i].e,map[i].v);
for i:=1 to n do
father[i]:=i;
qsort(1,m);
for i:=1 to m do
begin
if j=n-(k-1)-1
then
begin
break;
end;
if find(map[i].s)<>find(map[i].e)
then
begin
unite(map[i].s,map[i].e);
inc(j);
cost:=cost+map[i].v;
end;
end;
write(cost);
end.
###评测结果

测试数据 #0: Accepted, time = 0 ms, mem = 904 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 904 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 904 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 900 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 900 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 900 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 900 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 904 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 904 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 900 KiB, score = 10
Accepted, time = 15 ms, mem = 904 KiB, score = 100

kruskal

#include <cstdio>
#include <algorithm>
int n, m, kk;
struct edge {
    int u, v, q;
}a[500001];
int pr[5001], k[5001];
/*
inline int RD() {
    int x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9') {if (c == '-') f = -1;c = getchar();}
    while (c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}
}
*/
bool cmp(edge x, edge y) {
    return x.q < y.q;
}
int fr(int x) {
    int xr = x;
    while (pr[xr] != x) {
        x = pr[x];
//      printf ("%d %d\n", xr, x);
        xr = pr[xr];
        pr[x] = pr[xr];
    }
    return xr;
}
bool nv(int x, int y) {
    int xr, yr;
    xr = fr(x);
    yr = fr(y);
    if (xr == yr) return false;
    if (k[xr] > k[yr]) pr[yr] = xr;
    else if (k[yr] > k[xr]) pr[xr] = yr;
    else {
        pr[yr] = xr;
        ++k[xr];
    }
    return true;
}
int main() {
    int s = 0, tt = 0;
    scanf ("%d%d%d", &n, &m, &kk);
    for (int i = 1; i <= n; ++i) pr[i] = i;
    for (int i = 1; i <= m; ++i) {
        scanf ("%d%d%d", &a[i].u, &a[i].v, &a[i].q);
    }
    std::sort(a + 1, a + m + 1, cmp);
    for (int i = 1; i <= m; ++i) {
        if (nv(a[i].u, a[i].v)) {s += a[i].q; ++tt;}
        if (tt == n - kk) {printf ("%d\n", s); return 0;}
    }
    if (tt == n - kk) {printf ("%d\n", s); return 0;}
    else puts("No Answer\n");
}

//Kruskal轻松水过
#include<iostream>
#include<algorithm>
#include<stdlib.h>
using namespace std;
int d,fa[1001],ra[1001];
struct Edge
{
int a;
int b;
int v;
}edge[10001];
int ff(int a)
{
if (fa[a]==a)
return a;
else return ff(fa[a]);
}
bool hb(int a,int b)
{
int r1,r2;
r1=ff(a);
r2=ff(b);
if (r1==r2)
return false;
else
{
if (ra[r1]<ra[r2])
{
fa[r1]=r2;
ra[r2]+=ra[r1];
}
else
{
fa[r2]=r1;
ra[r1]+=ra[r2];
}
return true;
}
}
bool cmp(Edge a, Edge b)
{
return a.v<b.v;
}
int main()
{
int a,b,c,n,m,k,sum=0;
cin>>n>>m>>k;
d=n;
for(int i=1;i<=n;i++)
{
fa[i]=i;
ra[i]=1;
}
for (int i=1;i<=m;i++)
{
cin>>edge[i].a>>edge[i].b>>edge[i].v;

}
sort(edge+1,edge+1+m,cmp);
for (int i=1;i<=m;i++)
{
if (hb(edge[i].a,edge[i].b))
{
d--;
sum+=edge[i].v;
if (d==k)
{
cout<<sum;
return 0;
}
}
}
cout<<"No Answer";
return 0;

}

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

struct node
{
    int prev,next,weight;
    bool operator<(const node &t) const
    {
        if (weight!=t.weight) return weight<=t.weight;
            else return next>=t.next;
    }
}cloud[10050];

int num,n,m,Father[10050],Rank[10050],max_connect=0,ans,k;

void Init()
{
    for (int i=0;i<10050;i++)
    {
        Father[i]=i;
        Rank[i]=1;
    }
}

int Get_Father(int x)
{
    if (x==Father[x])
    {
        return x;
    }
    else
    {
        return Father[x]=Get_Father(Father[x]);
    }
}

void Merge(int a,int b)
{
    int xa=Get_Father(a),xb=Get_Father(b);
    if (xa!=xb)
    {
        Father[xb]=xa;
        Rank[xa]+=Rank[xb];
        max_connect++;
    }
}

bool Find(int a,int b)
{
    return (Get_Father(a)==Get_Father(b));
}

int main()
{
    cin >> n >> m >> k;
    max_connect=0;
    ans=0;
    Init();
    for (int i=1;i<=m;i++)
    {
        cin >> cloud[i].prev >> cloud[i].next >> cloud[i].weight; 
    }
    sort(cloud+1,cloud+m+1);
    for (num=1;num<=m;num++)
    {
        //cout << "***" << cloud[num].prev << " " << cloud[num].next << endl;
        if (!Find(cloud[num].prev,cloud[num].next))
        {
            Merge(cloud[num].prev,cloud[num].next);
            ans+=cloud[num].weight;
            //cout << cloud[num].weight << " " << max_connect << endl;
        }
        if (max_connect==n-k)
            break; 
    }
    if (max_connect!=n-k) cout << "No Answer" << endl;
        else cout << ans << endl;
    return 0;
}

裸kruskal，除了n-k要注意注意

这不是裸的kruskal吗

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int n,m,k,f[1010];
int ff(int x){return x==f[x]?x:f[x]=ff(f[x]);}
struct edge{
int l,r,v;
}e[10010];
bool cmp(edge a,edge b){return a.v<b.v;}
int main()
{
scanf("%d%d%d",&n,&m,&k);
int i,t=n,ans=0;
for(i=1;i<=m;++i)scanf("%d%d%d",&e[i].l,&e[i].r,&e[i].v);
sort(e+1,e+m+1,cmp);
for(i=1;i<=n;++i)f[i]=i;
for(i=1;i<=m;++i)
{
if(t<=k)break;
if(ff(e[i].l)!=ff(e[i].r))
f[ff(e[i].l)]=ff(e[i].r),ans+=e[i].v,t--;
}
if(t==k)cout<<ans;else cout<<"No Answer";
}


评测结果
编译成功

Free Pascal Compiler version 3.0.0 [2015/11/16] for i386
Copyright (c) 1993-2015 by Florian Klaempfl and others
Target OS: Win32 for i386
Compiling foo.pas
foo.pas(54,28) Warning: Variable "k" does not seem to be initialized
foo.pas(55,28) Warning: Variable "tot" does not seem to be initialized
foo.pas(7,7) Note: Local variable "j" not used
Linking foo.exe
64 lines compiled, 0.0 sec, 28080 bytes code, 1268 bytes data
2 warning(s) issued
1 note(s) issued
测试数据 #0: Accepted, time = 0 ms, mem = 924 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 924 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 920 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 924 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 924 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 924 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 924 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 920 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 924 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 924 KiB, score = 10
Accepted, time = 15 ms, mem = 924 KiB, score = 100
代码
program p1234;
type date=record
x,y,dis:longint;
end;
var a:array [0..10000] of date;
f:array [0..1000] of longint;
i,j,n,m,k,tot,k1,k2,p:longint;

procedure qsort(l,r:longint);
var i,j,mid:longint;
temp:date;
begin
i:=l;
j:=r;
mid:=a[(i+j) div 2].dis;
repeat
while a[i].dis<mid do inc(i);
while a[j].dis>mid do dec(j);
if i<=j then
begin
temp:=a[i];
a[i]:=a[j];
a[j]:=temp;
inc(i);
dec(j);
end;
until i>j;
if i<r then qsort(i,r);
if l<j then qsort(l,j);
end;

function sf(x:longint):longint;
begin
if x<>f[x] then sf:=sf(f[x])
else sf:=f[x];
f[x]:=sf;
end;

begin
readln(n,m,p);
for i:=1 to m do
begin
readln(a[i].x,a[i].y,a[i].dis);
end;
qsort(1,m);
for i:=1 to n do f[i]:=i;
for i:=1 to m do
begin
k1:=sf(a[i].x);
k2:=sf(a[i].y);
if k1<>k2 then
begin
f[k2]:=k1;
inc(k);
tot:=tot+a[i].dis;
end;
if k=n-p then
begin
writeln(tot);
halt;
end;
end;
writeln('No Answer');
end.

记录信息
评测状态 Accepted
题目 P1234 口袋的天空
递交时间 2016-03-23 21:37:38
代码语言 C++
评测机 ShadowShore
消耗时间 15 ms
消耗内存 632 KiB
评测时间 2016-03-23 21:37:39
评测结果
编译成功

foo.cpp: In function 'int main()':
foo.cpp:75:23: warning: unknown conversion type character 'l' in format [-Wformat=]
printf("%lld", Answer);
^
foo.cpp:75:23: warning: too many arguments for format [-Wformat-extra-args]
测试数据 #0: Accepted, time = 0 ms, mem = 628 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 628 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 628 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 628 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 624 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 628 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 624 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 632 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 632 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 628 KiB, score = 10
Accepted, time = 15 ms, mem = 632 KiB, score = 100
代码
#include<cstdio>
#include<algorithm>
using namespace std;

const int MaxN = 1000 + 10, MaxM = 10000 + 10;

int N, M, K, A, B;
long long Answer = 0;

struct finduniteNode {
int Parent;
bool notRoot;
}Node[MaxN];

struct eageStruction {
int From, Next, Cost;
bool operator < (const eageStruction &X) const {
return X.Cost > Cost;
}
}Eage[MaxM];

int getInt() {
int Return = 0;
char Get = getchar();
while(Get >= '0' && Get <= '9') {
Return = Return * 10 + (Get - '0');
Get = getchar();
}
return Return;
}

void Unite(const int &rootA, const int &rootB) {
if(Node[rootA].Parent < Node[rootB].Parent) {
Node[rootB].Parent += Node[rootA].Parent;
Node[rootA].notRoot = 1;
Node[rootA].Parent = rootB;
}
else {
Node[rootA].Parent += Node[rootB].Parent;
Node[rootB].notRoot = 1;
Node[rootB].Parent = rootA;
}
}

int Find(int Element, int theRoot, int parentNode) {
theRoot = parentNode = Element;
while(Node[theRoot].notRoot) theRoot = Node[theRoot].Parent;
while(Element != theRoot) {
parentNode = Node[Element].Parent;
Node[Element].Parent = theRoot;
Element = parentNode;
}
return theRoot;
}

int main() {
N = getInt(); M = getInt(); K = getInt();
if(M < N - K || N < K) {
printf("No Answer"); return 0;
}
for(int i = 1; i <= N; ++i) Node[i].Parent = i;
for(eageStruction *i = Eage + 1; i <= Eage + M; ++i) {
i->From = getInt();
i->Next = getInt();
i->Cost = getInt();
}
sort(Eage + 1, Eage + M + 1);
for(eageStruction *i = Eage + 1; i <= Eage + M && N > K; ++i) {
A = Find(i->From, 0, 0); B = Find(i->Next, 0, 0);
if(A != B) {
Unite(A, B); --N;
Answer = 1LL * (Answer + i->Cost);
}
}
printf("%lld", Answer);
return 0;
}

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1e4 + 10;

int N, M, K, ans, tot;
int fa[maxn];

struct edge{ int x, y, v; } es[maxn];
bool cmp(edge e1, edge e2) { return e1.v < e2.v; }

int find(int x) { return x == fa[x] ? x : find(fa[x]); }

void Kruskal() {
    sort(es + 1, es + 1 + M, cmp);
    for(int i = 1; i <= N; i++) fa[i] = i;
    for(int i = 1; i <= M && tot > K; i++) {
        int u = find(es[i].x), v = find(es[i].y);
        if(u != v) {
            fa[u] = v;
            ans += es[i].v;
            tot--;
        }
    }
}

int main() {
    scanf("%d%d%d", &N, &M, &K); tot = N;
    for(int i = 1; i <= M; i++) scanf("%d%d%d", &es[i].x, &es[i].y, &es[i].v);
    Kruskal();
    if(tot == K) printf("%d\n", ans);
    else printf("No Answer\n");
    
    return 0;
}

整整7次！终于A了！希望大家能一起不断的探索，不放弃地钻研，终会有结果的！！！

讲解请看楼下楼下的xuxianbo

附上我瞪大眼睛看了半小时才看出错误的代码：

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;

struct pathtype
{
int data;
int a;
int b;
};
int n , m , t , i , j , k , parent[1001] , ans = 0 , temp = 0;
pathtype daolu[10001];

int main()
{
scanf ("%d%d%d" , &n , &m , &t);
if (n < t || m < n - t)
{
printf ("No answer");
return 0;
}
for (i = 1; i <= m; i ++)
{
int x , y , z;
scanf ("%d%d%d" , &x , &y , &z);
daolu[i].data = z;
daolu[i].a = x;
daolu[i].b = y;
}
for (i = 1; i <= n; i ++)
parent[i] = i;

bool f = true;
i = 1;
while (f)
{
f = false;
for (j = 1; j <= m - i; j ++)
if (daolu[j].data > daolu[j + 1].data)
{
int x;
x = daolu[j].data;
daolu[j].data = daolu[j + 1].data;
daolu[j + 1].data = x;
x = daolu[j].a;
daolu[j].a = daolu[j + 1].a;
daolu[j + 1].a = x;
x = daolu[j].b;
daolu[j].b = daolu[j + 1].b;
daolu[j + 1].b = x;
f = true;
}
i ++;
}

for (i = 1; i <= m && temp < n - t; i ++)
{
if (parent[daolu[i].a] != parent[daolu[i].b])
{
temp ++;
ans += daolu[i].data;
for (j = 1; j <= n; j ++)
if (parent[j] == parent[daolu[i].b] && j != daolu[i].b)
parent[j] = parent[daolu[i].a];
parent[daolu[i].b] = parent[daolu[i].a];
}
}
if (temp < n - t)
{
printf ("No answer");
return 0;
}
printf ("%d" , ans);
return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct dian{
int from,to,money;
}a[100001];
int father[100001];
int comp(const dian&x,const dian&y)
{
return x.money<y.money;
}
int find(int t)
{
if(father[t]!=t){
father[t]=find(father[t]);
return father[t];
}
else{
return t;
}
}
int main()
{
int n,m,k,i,j,total=0,sum=0;
scanf("%d%d%d",&n,&m,&k);
if(m<n-k||n<k){
printf("No Answer");
return 0;
}
for(i=1;i<=m;i++){
scanf("%d%d%d",&a[i].from,&a[i].to,&a[i].money);
}
sort(a+1,a+m+1,comp);
for(i=1;i<=n;i++){
father[i]=i;
}
for(i=1;i<=m;i++){
int temp1=find(a[i].from);
int temp2=find(a[i].to);
if(temp1!=temp2){
father[temp1]=temp2;
sum+=a[i].money;
total++;
}
if(total==n-k){
break;
}
}
printf("%d",sum);
return 0;
}

代码。水过。。
type arr=record
l,r,z:longint;
end;
var a:array[1..10000]of arr;
f:array[1..1000]of longint;
i,n,m,k,ans,tot:longint;
procedure qsort(l,r: longint);
var i,j,x: longint;
y:arr;
begin
i:=l;
j:=r;
x:=a[(l+r) div 2].z;
repeat
while a[i].z<x do inc(i);
while x<a[j].z do dec(j);
if not(i>j) then
begin
y:=a[i];
a[i]:=a[j];
a[j]:=y;
inc(i);
j:=j-1;
end;
until i>j;
if l<j then qsort(l,j);
if i<r then qsort(i,r);
end;

function find(x:longint):longint;
begin
if f[x]=x then exit(x);
f[x]:=find(f[x]);
exit(f[x]);
end;

begin
readln(n,m,k);
tot:=n;
for i:=1 to n do f[i]:=i;
for i:=1 to m do
readln(a[i].l,a[i].r,a[i].z);
qsort(1,m);
for i:=1 to m do
begin
if tot=k then
begin
writeln(ans);
halt;
end;
if find(a[i].l)<>find(a[i].r) then
begin
f[find(a[i].l)]:=find(a[i].r);
dec(tot);
inc(ans,a[i].z);
end;
end;
if tot=k then writeln(ans) else writeln('No Answer');
end.

我用并查集过的，貌似与kruscal没多大关系吧。。话说这题目看了好久才看懂
program Project1;

type rec = record
x, y, cost: longint;
end;

var
a: array[1..10000] of rec;
id, size: array[1..1000] of longint;
ans, total, n, m, k, i, idx, idy: longint;

function find(k: longint): longint;

begin
while k <> id[k] do
begin
id[k] := id[id[k]];
k := id[k];
end;
find := id[k];
end;

procedure union(x, y: longint);

begin
if size[x] >= size[y] then
begin
id[y] := x;
size[x] := size[x] + size[y];
end
else
begin
id[x] := y;
size[y] := size[y] + size[x];
end;
end;

procedure qsort(l, r: longint);

var
i, j, x: longint;
t: rec;
begin
i := l;
j := r;
x := a[(l + r) shr 1].cost;
repeat
while a[i].cost < x do
Inc(i);
while a[j].cost > x do
Dec(j);
if i <= j then
begin
t := a[i];
a[i] := a[j];
a[j] := t;
Inc(i);
Dec(j);
end;
until i > j;
if i < r then
qsort(i, r);
if l < j then
qsort(l, j);
end;
begin
readln(n, m, k);
for i := 1 to n do
begin
id[i] := i;
size[i] := 1;
end;
for i := 1 to m do
readln(a[i].x, a[i].y, a[i].cost);
qsort(1, m);
total := n;
ans := 0;
for i := 1 to m do
begin
idx := find(a[i].x);
idy := find(a[i].y);
if idx <> idy then
begin
union(idx, idy);
Dec(total);
ans := ans + a[i].cost;
end;
if total = k then
break;
end;
if total > k then
writeln('No Answer')
else
writeln(ans);
readln;
end.

测试数据 #0: Accepted, time = 15 ms, mem = 548 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 552 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 548 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 552 KiB, score = 10

测试数据 #4: Accepted, time = 0 ms, mem = 552 KiB, score = 10

测试数据 #5: Accepted, time = 15 ms, mem = 552 KiB, score = 10

测试数据 #6: Accepted, time = 15 ms, mem = 548 KiB, score = 10

测试数据 #7: Accepted, time = 15 ms, mem = 552 KiB, score = 10

测试数据 #8: Accepted, time = 15 ms, mem = 548 KiB, score = 10

测试数据 #9: Accepted, time = 15 ms, mem = 548 KiB, score = 10

Accepted, time = 90 ms, mem = 552 KiB, score = 100

代码

#include <iostream>
#include <stdio.h>
#include <algorithm>

using namespace std;

long long n , m , k;
long long i , j;
long long now;
long long ans;

struct link
{
long long x , y , cost;
};

int cmp( link a , link b )
{
if( a.cost < b.cost )
return 1;
return 0;
}

int pre[ 10000 + 10 ];
link a[ 10000 + 10 ];

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

void merge( long long x , long long y )
{
pre[ find( x ) ] = find( y );
return;
}

int main()
{
scanf( "%lld %lld %lld" , &n , &m , &k );

if( k > n || n - m > k )
{
printf( "No Answer\n" );
return 0;
}

for( i = 1 ; i <= n ; i++ )
pre[i] = i;
for( i = 0 ; i < m ; i++ )
scanf( "%lld %lld %lld" , &a[i].x , &a[i].y , &a[i].cost );

sort( a , a + m , cmp );
now = n;
i = 0;
ans = 0;
while( now > k )
{
if( i >= m )
{
printf( "No Answer\n" );
return 0;
}
if( find( a[i].x ) != find( a[i].y ) )
{
merge( a[i].x , a[i].y );
now--;
ans += a[i].cost;
}
i++;
}
printf( "%lld\n" , ans );
return 0;
}

kruscal+quick sort+并查集
#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;
struct edge{
int from, to, len;
};
edge e[10005];
int node[1005];
int size;
int esize;
int tree;
void sort(int from, int to){
if (from >= to)return;
int i = from, j = to;
edge k = e[from];
while (true){
while (e[j].len > k.len)j--;
if (j == i)break;
e[i] = e[j];
e[j] = k;
i++;
while (e[i].len < k.len)i++;
if (j == i)break;
e[j] = e[i];
e[i] = k;
j--;
}
sort(from, i - 1);
sort(i + 1, to);
}
int father(int n){
while (node[n] != -1)n = node[n];
return n;
}
void kruscal(){
memset(node, -1, sizeof(node));
int i, j;
int ee = 0;
int cost = 0;
for (i = 0; i < esize&&ee < size - tree; i++){
int ff = father(e[i].from);
int tf = father(e[i].to);
if (ff != tf){
ee++;
cost += e[i].len;
node[ff]=tf;
}
}
if (ee == size - tree){
cout << cost << endl;
}
else
cout << "No Answer" << endl;
}
int main(){
freopen("in.txt", "r", stdin);
cin >> size >> esize >> tree;
int i;
for (i = 0; i < esize; i++)
cin >> e[i].from >> e[i].to >> e[i].len;
sort(0, esize - 1);
kruscal();
return 0;
}