1 条题解
-
0

// 最大生成树 Kruskal算法 O(MlogM) #include<bits/stdc++.h> #define int long long using namespace std; const int N=2010,M=4000010; int n,m,tot,ans,a[N],fa[N]; pair<int,pair<int,int> >e[M]; //边集 int find(int u){ //并查集的找根 return fa[u]==u?u:fa[u]=find(fa[u]); } void kruskal(){ sort(e+1,e+m+1); //排序 reverse(e+1,e+m+1); //逆序 for(int i=1; i<=n; i++) fa[i]=i; for(int i=1; i<=m; i++){ int x=find(e[i].second.first),y=find(e[i].second.second); if(x!=y){ fa[x]=y; ans+=e[i].first; if(++tot==n-1) break; } } cout<<ans; } signed main(){ cin>>n; for(int i=1,x;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++) for(int j=1;j<i;j++) e[++m]={a[i]^a[j],{i,j}}; kruskal(); }
- 1
信息
- ID
- 6722
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 8
- 标签
- 递交数
- 25
- 已通过
- 6
- 上传者