k算法最小生成树的最优化，例题PTA：毁灭

题目链接

校内链接:7-10 毁灭 - 测试模拟1,没有的依然可以看题目图片，在下面

题目

图解

parent数组进行set查找的路径压缩，cnt数组原理判断更少的set集合来更新新集合的parent

其他地方，排序依旧是堆排序，用优先队列，定义一个struct edge并重载 < 符号就好了

我们接下来只图解整个parent数组和cnt数组怎么使用

其实这里我们加一个判定，每回在对cnt进行操作的时候判断cnt的大小是否等于N就可以判断是否成功生成了最小生成树

这里我们例题是一个小变种我们要计算所有不在最小生成树的边的路径大小总和

代码

#include<iostream> #include<queue> using namespace std; const int N=2e5+5; int fa[N]; int cnt[N]; struct edge{ int u; int v; long long len; edge(int U=0,int V=0,int Len=0):u(U),v(V),len(Len){}; bool operator <(const edge& y)const{ return len>y.len; }; }; int findfa(int x) { if(fa[x]==x) return x; return findfa(fa[x]); } int main() { int n,m; long long sum;sum=0; priority_queue<edge>queue1; cin>>n>>m; for(int i=1;i<=n;i++) fa[i]=i,cnt[i]++; for(int i=0;i<m;i++) { int u,v,len; cin>>u>>v>>len; queue1.push(edge(u,v,len)); } while(!queue1.empty()) { edge ed=queue1.top(); queue1.pop(); int u=ed.u,v=ed.v,len=ed.len; int fau=findfa(u),fav=findfa(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(len>0) sum+=len; } cout<<sum; }

结果