1 条题解

  • 0
    @ 2026-6-15 11:45:59

    // 最大生成树 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

    D132 最小生成树 Kruskal 算法 [USACO15FEB] Superbull S

    信息

    ID
    6722
    时间
    1000ms
    内存
    128MiB
    难度
    8
    标签
    递交数
    25
    已通过
    6
    上传者