P1669 P1669 [USACO04DEC] Bad Cowtractors S
题意简化：在一个有 \(N\) 个点 \(M\) 条边的图中选出 \(N-1\) 条边构成一棵树，使得树的总边权最大，求最大总边权。
上述问题即为最小（大）生成树问题，本题为最大生成树，如有未详者可以移步 P3366。
该问题一般是 Kruskal 和 Prim 算法，下面提供代码。
- Kruskal 算法基于排序后的贪心，以并查集确保其正确性。复杂度 \(O(mlogm)\) 用得更多。
- Prim 算法更像是 Dijkstra，通过松弛操作不断更新入树路径。复杂度 \(O(n^2)\) 在稠密图中有应用。
- 注意这个图可能是不连通的，最后要判断是否选中了 \(N-1\) 条边。
- 经试，这道题并没有必要开 long long，似乎有两篇题解写错了。
Kruskal 版
// 2023/5/30 Author:ForMyDream
#include<iostream>
#include<algorithm>
#define maxn 20001
//#define int long long
using namespace std;
int n,m,head[maxn],cnt,fa[maxn],ans,tot;
struct Edge{ int u,v,nxt,w; }edge[maxn];
bool cmp(Edge a,Edge b){ return a.w>b.w; }
void add(int u,int v,int w){
edge[++cnt].v=v,edge[cnt].u=u,edge[cnt].w=w,
edge[cnt].nxt=head[u],head[u]=cnt;
}
int find(int x){ return x==fa[x] ? x : fa[x]=find(fa[x]); }
int merge(int x,int y){
int fx=find(x),fy=find(y);fa[fx]=fa[fy];
}
void Kruskal(){
sort(edge+1,edge+m+1,cmp);
for (int i=1;i<=m;i++){
int fu=find(edge[i].u),fv=find(edge[i].v);
if (fu==fv) continue;
merge(fu,fv);
ans+=edge[i].w,tot++;
// printf("选中%d-%d\n",edge[i].u,edge[i].v);
}
}
signed main(){
cin>>n>>m; int u,v,w;
for (signed i=1;i<=m;i++){ cin>>u>>v>>w; add(u,v,w); }
for (signed i=1;i<=n;i++) fa[i]=i;
Kruskal();
if (tot!=n-1) cout<<-1;
else cout<<ans;
return 0;
}
Prim 版
标签：cnt,int,最小,long,生成,fa,edge,LuoguP1669,find From： https://www.cnblogs.com/CZXsNote/p/17443417.html