P1195 口袋的天空

题目背景

小杉坐在教室里，透过口袋一样的窗户看口袋一样的天空。

有很多云飘在那里，看起来很漂亮，小杉想摘下那样美的几朵云，做成棉花糖。

题目描述

给你云朵的个数N，再给你M个关系，表示哪些云朵可以连在一起。

现在小杉要把所有云朵连成K个棉花糖，一个棉花糖最少要用掉一朵云，小杉想知道他怎么连，花费的代价最小。

输入输出格式

输入格式：

每组测试数据的

第一行有三个数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

输出格式：

对每组数据输出一行，仅有一个整数，表示最小的代价。

如果怎么连都连不出K个棉花糖，请输出'No Answer'。

输入输出样例

输入样例#1：

3 1 2
1 2 1

输出样例#1：

说明

厦门一中YMS原创

分析：

1.这道题题意是让你在求最小生成树的时候特判，判断什么时候停止粘合节点

2.于题意，我们便在普通的kruskal算法做点小修改，直接在制造最小生成树的时候判断节点数与K值得关系即可

基本上可以套用最小生成树的算法

改几句话就可以了,

下面给出代码及部分注释

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 int en,f[10009],m,n,siz,k;
 5 struct edge{
 6     int s,e,d;
 7 }ed[10009];
 8 void add_edge(int s,int e,int d){
 9     en++;
10     ed[en].s = s;ed[en].e = e; ed[en].d = d; 
11 }
12 bool operator < (const edge &a,const edge &b){
13     return a.d < b.d;
14 }
15 int getf(int now){
16     if(f[now] == now)return now;
17     else return f[now] = getf(f[now]);
18 }
19 int kruskal(){
20     sort(ed+1,ed+1+m);
21     for(int a = 1; a <= n;a++)f[a] = a;
22     int ans = 0;
23     siz = n;
24     for(int i = 1; i <= m; i++){
25         int f1 = getf(ed[i].s);
26         int f2 = getf(ed[i].e);
27         if(f1 != f2){
28             ans += ed[i].d;
29             siz--;                 //两节点粘合之后棉花糖数量减一 
30             f[f1] = f2;
31         }
32         if(siz == k)return ans;   //符合答案要求，可以组成K个棉花糖 ，则返回答案
33     }
34     return -1;                      //如果之前没有直接返回答案，则说明不能组成K个棉花糖则返回-1 
35 }
36 int main(){
37     scanf("%d%d%d",&n,&m,&k);
38     for(int i = 1; i <= m; i++){
39         int u,v,d;
40         scanf("%d%d%d",&u,&v,&d);
41         add_edge(u,v,d);
42     }
43     int ans = kruskal();
44     if(ans == -1)printf("No Answer
");  //无答案 
45     else printf("%d
",ans);            //输出 
46     return 0;
47 }

两个低级错误，搞死我

1、第21行，if(x==f[x]) return x;// x==f[x]写成了x=f[x]

2、第22行，else return f[x]=find(f[x]);//这里写成了f[x]=f[f[x]]

3、错了的话，一定是自己代码哪里有问题

 1 #include <bits/stdc++.h>
 2 const int MAXN=1e4+10;
 3 using namespace std;
 4 struct node{
 5     int u,v,w;
 6     bool operator <(const node &p) const{
 7         return w<p.w;
 8     }
 9 }g[MAXN];
10 int f[MAXN];
11 int n,m,k;
12 
13 void init(){
14     cin>>n>>m>>k;
15     for(int i=1;i<=m;i++) cin>>g[i].u>>g[i].v>>g[i].w;
16     for(int i=1;i<=n;i++) f[i]=i;
17     sort(g+1,g+1+m);
18 }
19 
20 int find(int x){
21     if(x==f[x]) return x;// x==f[x]写成了x=f[x] 
22     else return f[x]=find(f[x]);//这里写成了f[x]=f[f[x]] 
23 }
24 
25 int kruskal(){
26     int n1=n,w=0;
27     for(int i=1;i<=m;i++){
28         int x=find(g[i].u);
29         int y=find(g[i].v);
30         if(x!=y){
31             f[y]=x;
32             n1--;
33             w+=g[i].w;
34         }
35         if(n1==k) return w;
36     }
37     return -1;
38 }
39 
40 int main(){
41     //freopen("in2.txt","r",stdin);
42     init();
43     int ans=kruskal();
44     if(ans==-1) cout<<"No Answer"<<endl;
45     else  cout<<ans<<endl;
46     return 0;
47 }