最小生成树模板如何应用于实际问题？

本文共计272个文字，预计阅读时间需要2分钟。

请提供需要改写的伪原创开头内容，我将为您进行改写。

#include<bits/stdc++.h> using namespace std; typedef long long ll; #define inf 0x3f3f3f3f struct Edge { int u,v,w; }edge[MAXM]; int tot; void addedge(int u,int v,int w) { edge[tot].u=u; edge[tot].v=v; edge[tot++].w=w; }// 注意 加边时是有向边！！！ // 所以如果是无向图求最小生成树的话， // addedge( u,v,w ), addedge( v,u,w ) 两次加边 ( 即反向 )即可 bool cmp(Edge a,Edge b) { return a.w<b.w; } int Find(int x) { if(F[x]==-1)return x; else return F[x]=Find(F[x]); } int kruskal(int n) { memset(F,-1,sizeof(F)); sort(edge,edge+tot,cmp); int cnt=0; int ans=0; for(int i=0;i<tot;i++){ int u=edge[i].u; int v=edge[i].v; int w=edge[i].w; int t1=Find(u); int t2=Find(v); if(t1!=t2){ ans+=w; F[t1]=t2; cnt++; } if(cnt==n-1)break; } if(cnt<n-1)return -1;// 图不连通 else return ans;// 最小生成树权值 }