电子产品东莞网站建设,商城网站建设案例,专门制作网页的公司,许昌市住房和城乡建设局门户网站明显看出为最小生成树#xff0c;那么#xff1a;难点在哪里呢#xff1f;if(cntn-k)//******{flag1;break;}为什么是cntn-k呢而不是k呢#xff1f;#xff01;#xff01;#xff01;解释#xff1a;#xff08;如果每个已经连在一起了就不能分开#xff0c;不管多少…明显看出为最小生成树那么难点在哪里呢 if(cntn-k)//******{flag1;break;}为什么是cntn-k呢而不是k呢解释如果每个已经连在一起了就不能分开不管多少个连在一起的算一个棉花糖***上先在有两棵树也就是有两个棉花糖虽然1那边有三个点连接在一起但是它们联通了就只算一个数不能分开。以此类推 有一句话说的是 如果n个点被n-1条边连接的话这一定是棵树。那么连的边数 得到的树的个数n-1 1(全部点都连接在一起了)n-2 2还剩一个点没有连接在一起结果就是分成两部分一个点的和剩下所有点的n-3 3以此类推... ...n-k k所以我们如果想要连出k棵树就需要连n-k条边。题目要求用n朵云连出k个棉花糖。因为每个棉花糖都是连通的那么每个棉花糖就相当于是一棵树。就是说要用n个节点连出k棵树。也就是说要用n-k条边连出k棵树。也就是说要花费连出n-k条边的代价。既然一定要花费连出n-k条边的代价那么当然要选择代价最小的边连起来。所以给每条可以连的边按代价从小到大排个序然后连n-k条边造k个最小生成树就可以了。如果给的关系数m小于需要连的边数n-k是一定连不出k个树来的因为m个关系只能连m条边。#includeiostream
#includealgorithm
using namespace std;
const int N1e310,M1e410;
struct edge{int u,v,w;
}e[M];
int fa[N],n,m,k;
bool cmp(edge a,edge b)
{return a.wb.w;
}
int find(int x)
{if(fa[x]x)return x;else{fa[x]find(fa[x]);return fa[x];}
}
int main()
{cinnmk;for(int i1;im;i){cine[i].ue[i].ve[i].w;}for(int i1;in;i){fa[i]i;}sort(e1,e1m,cmp);int flag0,cnt0,sum0;for(int i1;im;i){int f1find(e[i].u);int f2find(e[i].v);if(f1!f2){fa[f1]f2;cnt;sume[i].w;}if(cntn-k)//******{flag1;break;}}if(flag)coutsum;elsecoutNo Answer;return 0;
}
