P4826 [USACO15FEB]Superbull S

最大生成树,暴力加贪心;

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N = 2007;
ull id[N];
int f[N];
struct Node{
  int i, j;
  ull v;
}a[N * N];
int find (int x) { return f[x] == x ? x : f[x] = find (f[x]); }
bool cmp (Node a, Node b) { return a.v > b.v; }
int main(){
  int n;
  scanf(“%d”, &n);
  for(int i = 1;i <= n;i ++) scanf(“%lld”, &id[i]), f[i] = i;
  int cnt = 0;
  for(int i = 1;i < n;i ++)
    for(int j = i + 1;j <= n;j ++)
      a[++ cnt].i = i, a[cnt].j = j, a[cnt].v = id[i] ^ id[j];
  sort(a + 1, a + cnt + 1, cmp);
  ull ans = 0;
  for(int i = 1;i < cnt;i ++){
    int fx = find (a[i].i), fy = find (a[i].j);
    if(fx != fy)
      f[fx] = fy, n –, ans += a[i].v;
    if(n == 1){
      printf(“%lld”, ans);
      return 0;
    }
  }
  return 0;
}

原文地址:http://www.cnblogs.com/loser–QAQ/p/16852531.html

发表评论

您的电子邮箱地址不会被公开。