题目
思路
这是一道明显的最大生成树问题,算法和最小生成树一样,有Prim算法和Kruskal算法,只是把最小边改为最大边而已。我用的是Kruskal算法。
代码
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<iostream> using namespace std; struct node { int x; int y; int z; }; node a[20001]; int father[1001],ans=0,k=0,n,m; int find(int b) { if(b!=father[b]) father[b]=find(father[b]); return father[b]; } void unionn(int b,int c) { int d=find(b),e=find(c); father[d]=e; } bool cmp(node b,node c) { return b.z>c.z; } int main() { cin>>n>>m; for(int i=1;i<=m;i++) cin>>a[i].x>>a[i].y>>a[i].z; for(int i=1;i<=n;i++) father[i]=i; sort(a+1,a+m+1,cmp); for(int i=1;i<=m;i++) { if(find(a[i].x)!=find(a[i].y)) { unionn(a[i].x,a[i].y); ans=ans+a[i].z; k++; } if(k==n-1) break; } if(k==n-1) cout<<ans<<endl; else cout<<-1<<endl; return 0; }