手机微信一体网站建设手机网站生成小程序

手机微信一体网站建设,手机网站生成小程序,中国最有名的建设网站,金华网站建设luopan题目链接 校内链接:7-10 毁灭 - 测试模拟1,没有的依然可以看题目图片#xff0c;在下面 题目 图解 parent数组进行set查找的路径压缩#xff0c;cnt数组原理判断更少的set集合来更新新集合的parent 其他地方#xff0c;排序依旧是堆排序#xff0c;用优先队列#xff…题目链接校内链接:7-10 毁灭 - 测试模拟1,没有的依然可以看题目图片在下面题目图解parent数组进行set查找的路径压缩cnt数组原理判断更少的set集合来更新新集合的parent其他地方排序依旧是堆排序用优先队列定义一个struct edge并重载 符号就好了我们接下来只图解整个parent数组和cnt数组怎么使用其实这里我们加一个判定每回在对cnt进行操作的时候判断cnt的大小是否等于N就可以判断是否成功生成了最小生成树这里我们例题是一个小变种我们要计算所有不在最小生成树的边的路径大小总和代码#includeiostream #includequeue using namespace std; const int N2e55; int fa[N]; int cnt[N]; struct edge{ int u; int v; long long len; edge(int U0,int V0,int Len0):u(U),v(V),len(Len){}; bool operator (const edge y)const{ return leny.len; }; }; int findfa(int x) { if(fa[x]x) return x; return findfa(fa[x]); } int main() { int n,m; long long sum;sum0; priority_queueedgequeue1; cinnm; for(int i1;in;i) fa[i]i,cnt[i]; for(int i0;im;i) { int u,v,len; cinuvlen; queue1.push(edge(u,v,len)); } while(!queue1.empty()) { edge edqueue1.top(); queue1.pop(); int ued.u,ved.v,lened.len; int faufindfa(u),favfindfa(v); if(fau!fav) { if(cnt[fav]cnt[fau]) { fa[fau]fa[fav]; cnt[fav]cnt[fau]; } else { fa[fav]fa[fau]; cnt[fau]cnt[fav]; } } else if(len0) sumlen; } coutsum; }结果