题目背景
小杉坐在教室里,透过口袋一样的窗户看口袋一样的天空。
有很多云飘在那里,看起来很漂亮,小杉想摘下那样美的几朵云,做成棉花糖。
题目描述
给你云朵的个数 $N$ ,再给你 $M$ 个关系,表示哪些云朵可以连在一起。
现在小杉要把所有云朵连成 $K$ 个棉花糖,一个棉花糖最少要用掉一朵云,小杉想知道他怎么连,花费的代价最小。
输入格式
、
每组测试数据的
第一行有三个数 $ N,M,K(1 \le N \le 1000,1 \le M \le 10000,1 \le K \le 10) $
接下来 $M$ 个数每行三个数 $X,Y,L$ ,表示 $X$ 云和 $Y$ 云可以通过 $L$ 的代价连在一起。 $(1 \le X,Y \le N,0 \le L<10000)$
$30%$ 的数据 $N \le 100,M \le 1000N≤100,M≤1000$
输出格式
对每组数据输出一行,仅有一个整数,表示最小的代价。
如果怎么连都连不出 $K$ 个棉花糖,请输出No Answer
。
输入样例
3 1 2
1 2 1
输出样例
1
Solution
这道题可用并查集来做,先把代价排序,然后合并,如果在同一集合,则不合并。
每合并一次就会减少一个连通块。
其实这就是Kruskal
最小生成树的思想。
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
| #include<iostream> #include<cstdio> #include<algorithm> using namespace std; struct Edge{ int u,v,w; } e[200002]; int fa[200002]={0}; int find(int x){ if(fa[x]!=x) fa[x]=find(fa[x]); return fa[x]; } int un(int x,int y){ fa[x]=y; } bool cmp(Edge a,Edge b){ return a.w<b.w; } int main(){ int n,m,k,ans=0; cin>>n>>m>>k; for(int i=1;i<=n;i++){ fa[i]=i; } for(int i=1;i<=m;i++){ scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w); } int u=0; int p=n-k; int q=0; sort(e+1,e+1+m,cmp); for(int i=1;i<=m;i++){ int x,y; x=find(e[i].u); y=find(e[i].v); if(x==y){ goto exit; } else{ un(x,y); q++; ans+=e[i].w; } if(q==p){ break; } exit: u=0; } cout<<ans; }
|