首页 > 代码库 > vijos 天空
vijos 天空
背景 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<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<string>
using namespace std;
int n,m,k,set[110],cost[110],used[110];
bool flag;
struct line
{
int x,y,c;
}list[110];
bool cmp(line l,line t)
{
return l.c<t.c;
}
int find(int x)
{
if(set[x]!=x) set[x]=find(set[x]);
return set[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);
sort(list+1,list+1+m,cmp);
for(int i=1;i<=n;i++)
set[i]=i,cost[i]=0;
for(int i=1;i<=m;i++)
{
int x,y;
x=find(list[i].x);
y=find(list[i].y);
if(x!=y)
{
set[x]=y;
used[i]=true;
cost[x]+=cost[y]+list[i].c;
}
}
int maxx=0;
for(int i=1;i<=n;i++)
if(set[i]==i)
maxx++;
if(maxx>k)
printf("NO ANSWER\n");
else
{
int sum=0;
for(int i=1;i<=m;i++)
sum+=cost[i];
if(maxx==k)
printf("%d\n",sum);
else
{
for(int i=m;i>=1;i--)
{
if(used[i])
{
sum=sum-list[i].c;
maxx++;
if(maxx==k)
{
flag=true;
break;
}
}
}
if(flag) printf("NO ANSWER\n");
else printf("%d\n",sum);
}
}
return 0;
}
vijos 天空