洛谷 P1195 口袋的天空-白红宇

洛谷 P1195 口袋的天空

阅读量：4992 次

发布时间：2019-06-12

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

题目背景

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

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

题目描述

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

输出样例#1：

说明

厦门一中YMS原创

————————————————--我是分割线————————————————————

1 /*  2     Problem:  3     OJ:  4     User:S.B.S.  5     Time:  6     Memory:  7     Length:  8 */  9 #include
      
        10 #include
       
         11 #include
        
          12 #include
         
           13 #include
          
            14 #include
           
             15 #include
            
              16 #include
             
               17 #include
              
                18 #include
               
                 19 #include
                
                  20 #include
                 
                   21 #include
                  
                    22 #include
                   
                     23 #include
                    
                      24 #include
                      25 #define maxn 1001 26 #define F(i,j,k) for(int i=j;i<=k;i++) 27 #define rep(i,j,k) for(int i=j;i
                      
                       =k;i--) 30 #define inf 0x3f3f3f3f 31 #define maxm 10001 32 #define mod 998244353 33 //#define LOCAL 34 using namespace std; 35 inline int read(){ 36 int x=0,f=1;char ch=getchar(); 37 while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} 38 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 39 return x*f; 40 } 41 inline void out(int n){ 42 if(n<0){putchar('-');n=0-n;} 43 if(n>=10) out(n/10); 44 putchar((n%10)+'0'); 45 return; 46 } 47 int n,m,k; 48 int tot,ans,cnt; 49 struct EDGE 50 { 51 int from; 52 int to; 53 int value; 54 }e[maxm]; 55 int fa[maxn],rank[maxn]; 56 inline void addedge(int u,int v,int w) 57 { 58 tot++; 59 e[tot].from=u; 60 e[tot].to=v; 61 e[tot].value=w; 62 return; 63 } 64 bool cmp(EDGE a,EDGE b) { return a.value
                       
                        rank[y]) fa[x]=y; 72 else{ 73 fa[y]=x; 74 if(rank[x]==rank[y]) rank[y]++; 75 } 76 } 77 int d[maxm],cur; 78 inline void kruscal() 79 { 80 init();sort(e+1,e+m+1,cmp); 81 F(i,1,m){ 82 int a=find(e[i].from),b=find(e[i].to); 83 if(a==b) continue; 84 else{ 85 d[++cur]=i;cnt++;ans+=e[i].value; 86 Union(e[i].from,e[i].to); 87 } 88 if(cnt==(n-k)) break; 89 } 90 } 91 int main() 92 { 93 std::ios::sync_with_stdio(false);//cout<
                        
                         <
                         
                          <
                          
                           >n>>m>>k; 99 F(i,1,m){100 int a,b,c;cin>>a>>b>>c;101 addedge(a,b,c);102 }103 kruscal();104 cout<
                           
                            <