背景

小杉坐在教室里，透過口袋一樣的窗戶看口袋一樣的天空。

有很多云飄在那里，看起來很漂亮，小杉想摘下那樣美的幾朵云，做成棉花糖。

描述

給你云朵的個數(shù)N，再給你M個關系，表示哪些云朵可以連在一起。

現(xiàn)在小杉要把一些云朵連在一起，做成K個棉花糖，一個棉花糖最少要用掉一朵云，小杉想知道他怎么連，花費的代價最小。

格式

輸入格式

每組測試數(shù)據(jù)的
第一行有三個數(shù)N,M,K(1<=N<=1000,1<=M<=10000,1<=K<=10)
接下來M個數(shù)每行三個數(shù)X,Y,L，表示X云和Y云可以通過L的代價連在一起。(1<=X,Y<=N,0<=L<10000)
30%的數(shù)據(jù)N<=100,M<=1000

輸出格式

對每組數(shù)據(jù)輸出一行，僅有一個整數(shù)，表示最小的代價。

如果怎么連都連不出K個棉花糖，請輸出'No Answer'。

樣例1

樣例輸入1[復制]

3 1 2 1 2 1

樣例輸出1[復制]

1

限制

每個測試點1s

提示

樣例2：
Input:
3 1 1
1 2 1

Output:
No Answer

因為單個云可以做成一個棉花糖，所以顯然我們要做（k-1）個一朵云的棉花糖，也就是用生成一個n-1—（k-1）=n-k條邊的最小生成樹，kruskal。 并查集寫掛了,WA了TM整整6次！ 1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<iostream> 6 #include<vector> 7 #include<map> 8 #include<set> 9 #include<stack> 10 #include<string> 11 #include<algorithm> 12 #define maxn 10000+50 13 #define inf 0x7fffffff 14 #define xiao 1e-9 15 using namespace std; 16 int fa[maxn],sum=0; 17 struct Edge{int x,y,v;}edge[10000+5]; 18 int find(int x) 19 { 20 if(fa[x]!=x) fa[x]=find(fa[x]); 21 return fa[x]; 22 } 23 int cmp(const Edge &a,const Edge &b) 24 { 25 if(a.v<b.v) return 1; 26 else return 0; 27 } 28 int main() 29 { 30 int n,m,k,x,y,z,tot=0,ans=0; 31 scanf("%d%d%d",&n,&m,&k); 32 if(m<n-k||n<k) {printf("No Answer");return 0;} 33 for(int i=1;i<=m;++i) 34 { 35 scanf("%d%d%d",&x,&y,&z); 36 edge[i].x=x;edge[i].y=y;edge[i].v=z; 37 } 38 sort(edge+1,edge+m+1,cmp); 39 for(int i=1;i<=n;++i) fa[i]=i; 40 for(int i=1;i<=m;++i) 41 { 42 int faa=find(edge[i].x); 43 int fab=find(edge[i].y); 44 if(faa!=fab) 45 { 46 fa[faa]=fab; 47 ans+=edge[i].v; 48 sum++; 49 } 50 if(sum==n-k) {break;} 51 } 52 cout<<ans; 53 return 0; 54 } 55 56 57

?

轉載于:https://www.cnblogs.com/TYH-TYH/p/4938441.html

總結

以上是生活随笔為你收集整理的VIJOS【1234】口袋的天空的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。