背景 Background
小杉坐在教室里，透过口袋一样的窗户看口袋一样的天空。
有很多云飘在那里，看起来很漂亮，小杉想摘下那样美的几朵云，做成棉花糖。
描述 Description
给你云朵的个数N，再给你M个关系，表示哪些云朵可以连在一起。
现在小杉要把所有云朵连成K个棉花糖，一个棉花糖最少要用掉一朵云，小杉想知道他怎么连，花费的代价最小。
输入格式 Input Format
每组测试数据的
第一行有三个数N,M,K(1<=N<=1000,1<=M<=10000,1<=K<=10)
接下来M个数每行三个数X,Y,L，表示X云和Y云可以通过L的代价连在一起。(1<=X,Y<=N,0<=L<10000)
30%的数据N<=100,M<=1000
输出格式 Output Format
对每组数据输出一行，仅有一个整数，表示最小的代价。
如果怎么连都连不出K个棉花糖，请输出'No Answer'。
样例输入 Sample Input
3 1 2
1 2 1
样例输出 Sample Output
1
时间限制 Time Limitatio
每个测试点1s
注释 Hint
样例2：
Input:
3 1 1
1 2 1
Output:
No Answer
分析：
这个题其实很简单，就是尽量生成最小生成树（用克鲁斯卡尔算法，PS：传说中的kruskal，先排序，后贪心的算法），有可能图不是连通的，也就是，给的数据是好几个图，这样，我们将要求的最小生成树的个数设为k，我们生成的最小生成树的个数是m，若m=k，则直接输出代价就可以了，如果m>k则说明图的个数比要求的最小生成树个数小，怎么也无法构成k个最小生成树，也就是输出"No Answer"
如果m<k说明，求出的最小生成树个数比要求的最小生成树少，这里，我们可以用剪断枝的方法来将一棵树砍成两棵（PS：刚才是剪，现在怎么砍了？），此时，用贪心将用过的边最长的砍掉，然后，判断砍断后的树的数量是否与要求的数量相同，如果不相同就再砍掉当前的最长边，直到现在树的数目与所求数目相同时就输出，当然，还存在着如果把所有的用到的枝都砍掉还是不能凑够k时再输出"No Answer"
【参考程序】：
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
struct node
{
int x,y,c;
} list[10010];
int fa[1010],cost[1010];
bool used[10010];
int n,m,k;
int cmp(const void *s,const void *t)
{
node i=*(node *)s,j=*(node *)t;
return i.c-j.c;
}
int Find(int x)
{
if (fa[x]!=x) fa[x]=Find(fa[x]);
return fa[x];
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for (int i=1;i<=m;i++)
scanf("%d%d%d",&list[i].x,&list[i].y,&list[i].c);
qsort(list+1,m,sizeof(node),cmp);
for (int i=1;i<=n;i++)
{
fa[i]=i; cost[i]=0;
}
memset(used,false,sizeof(used));
int x,y;
for (int i=1;i<=m;i++)
{
x=Find(list[i].x);
y=Find(list[i].y);
if (x!=y)
{
used[i]=true;
fa[y]=x;
cost[x]+=cost[y]+list[i].c;
}
}
int Max,scost,cut;
bool bk;
Max=0;
for (int i=1;i<=n;i++)
if (fa[i]==i) Max++;
if (Max>k) printf("No Answer\n");
else
{
scost=0;
for (int i=1;i<=n;i++)
if (fa[i]==i) scost+=cost[i];
if (Max==k) printf("%d\n",scost);
else
{
cut=0; bk=false;
for (int i=m;i>=1;i--)
if (used[i])
{
cut++;
scost-=list[i].c;
if (Max+cut==k)
{
bk=true; break;
}
}
if (!bk) printf("No Answer\n");
else printf("%d\n",scost);
}
}
return 0;
}
【参考程序】：//pascal
Type jilu=record
f,t,l:integer;
End;
Var n,m,k,i,s,max,cut:longint;
map:array[1..10000]of jilu;
use:array[1..10000]of boolean;
father,cost:array[1..1000]of longint;
bool:boolean;
x,y:integer;
Function find(now:integer):integer;
Begin
While father[father[now]]<>father[now] do
father[now]:=father[father[now]];
find:=father[now];
End;
Procedure csfp(be,en:integer);
Var x,y:integer;
bz:jilu;
Begin
x:=be; y:=en; bz:=map[be];
While x<y do
Begin
While (x<y)and(map[y].l>=bz.l) do dec(y);
map[x]:=map[y];
While (x<y)and(map[x].l<=bz.l) do inc(x);
map[y]:=map[x];
End;
map[x]:=bz;
If be<=x-1 Then csfp(be,x-1);
If x+1<=en Then csfp(x+1,en);
End;
Begin
Readln(n,m,k);
For i:= 1 to m do
Readln(map[i].f,map[i].t,map[i].l);
csfp(1,m);
For i:= 1 to n do father[i]:=i;
For i:= 1 to m do
Begin
x:=find(map[i].f);
y:=find(map[i].t);
If x<>y Then
Begin
use[i]:=true;
father[y]:=x;
cost[x]:=cost[x]+cost[y]+map[i].l;
End;
End;
For i:= 1 to n do
If father[i]=i Then inc(max);
If max>k Then Writeln('No Answer')
Else
Begin
For i:= 1 to n do
If father[i]=i Then s:=s+cost[i];
If k=max Then Writeln(s)
Else
Begin
bool:=false;
For i:= m downto 1 do
If use[i] Then
Begin
inc(cut);
s:=s-map[i].l;
If max+cut=k Then
Begin
Bool:=true; Break;
End;
End;
If bool Then Writeln(s)
Else Writeln('No Answer');
End;
End;
End.