Luogu4826 [USACO15FEB]Superbull 超级牛

发布于 2019-10-16  315 次阅读


Link

题意

n 头牛, 要求在它们中间安排 n-1 场决斗, 其中每场的收益是这两头牛权值的异或和, 使总的异或和最大

题解

longge说:

这题不是傻逼题嘛

确实比较简单

首先由题可知, 每头牛之间都可以有决斗,抽象成一张图,这是一张完全图,要求你在这张完全图中选出 n -1 条边, 使得边权总和最大.

很明确就是处理每头牛之间的权值异或和建图跑一个最大生成树.

觉得难度评分明显过高.

Code

#include <bits/stdc++.h>
using namespace std;

const int SIZE = 2000 + 5;
const int SIZE_EDGE = 2000 * 2000 + 5;

#define int long long

int n, num;
int id[SIZE], fa[SIZE];

struct node {
    int from, to, v;
} edge[SIZE_EDGE];

inline int read()
{
    char ch = getchar();
    int f = 1, x = 0;
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
    return x * f;
}

inline void Addedge(int x, int y, int z)
{
    edge[++num].from = x;
    edge[num].to = y;
    edge[num].v = z;
}

inline int Find(int x) { return fa[x] == x ? x : fa[x] = Find(fa[x]); }

inline void Unite(int x, int y)
{
    int fx = Find(x), fy = Find(y);
    if (fx != fy) fa[fx] = fy;
} 

inline int CMP(node a, node b) { return a.v > b.v; }

inline void Kruskal()
{
    int sum = 0, cnt = 0;
    for (int i = 1; i <= num; i++) {
        int u = edge[i].from, v = edge[i].to;
        if (Find(u) != Find(v)) {
            Unite(u, v);
            sum += edge[i].v, cnt++;
        }
        if (cnt == n - 1) break;
    }
    std::cout << sum;
} 

signed main()
{
    n = read();
    for (int i = 1; i <= n; i++) id[i] = read();
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            // if (i == j) continue;
            Addedge(i, j, id[i] ^ id[j]);
            // printf("%d %d %d\n", i, j, id[i] ^ id[j]);
        }
    }
    std::sort(edge + 1, edge + num + 1, CMP);
    for (int i = 1; i <= n; i++) fa[i] = i;
    Kruskal();
    return 0;
}

朴实沉毅