vijos P1234口袋的天空(Kruskal)(最小生成树)-白红宇

vijos P1234口袋的天空(Kruskal)(最小生成树)

阅读量：6088 次

发布时间：2019-06-20

本文共 1281 字，大约阅读时间需要 4 分钟。

P1234口袋的天空

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

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

描述

给你云朵的个数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

样例输入1

3 1 21 2 1

样例输出1

限制

每个测试点1s

提示

样例2：

Input:

3 1 1

1 2 1

Output:

No Answer

【分析】这个最小生成树题很有意思，他要求K个最小生成树，因为共有n朵云并且一朵云就可以构成一个棉花糖，所以不用云构造花费为0，那么就要留出k-1朵云单独作为一个棉花糖，即将剩下的n-（k-1）朵云构造成一棵最小生成树，即当加入的边数=n-(k-1)-1时构造完成。此时构造的为最小生成树，构造这个棵树花费最小，其他花费为0，所以这样就以最小的花费构造出了k个棉花糖；

算法以并查集优化的kruscal来构造即可。

#include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      #include
                      
                       #define mod 1000000007#define inf 0x3f3f3f3f#define pi acos(-1.0)using namespace std;typedef long long ll;const int N=1005;struct Edg{ int v,u;int w;}edg[300*300+50];bool cmp(Edg g,Edg h){ return g.w
                       
                        =n-(k-1)-1){ printf("%d\n",sum); break; } } if(num

View Code

转载于:https://www.cnblogs.com/jianrenfang/p/5728316.html

你可能感兴趣的文章