[BZOJ3943][Usaco2015 Feb]SuperBull 最大生成树


原题链接
注意到:
1.每个队伍都必须参加至少一次比赛
2.由于淘汰赛制,比赛关系不能成环
可知求的是一棵最大生成树.kruskal可过.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 2333
using namespace std;
typedef long long ll;
int n,a[N],cnt;
ll ans;
struct Node
{
    int x,y,z;
}e[N*N];
inline bool operator<(const Node &x,const Node &y)
{
    return x.z>y.z;
}
int fa[N];
int find(int x)
{
    return x==fa[x]?x:(fa[x]=find(fa[x]));
}
int main()
{
    cin>>n;
    for(int j,i=1;i<=n;++i)
    {
        fa[i]=i;
        scanf("%d",&a[i]);
        for(j=1;j<i;++j)
        {
            cnt++;
            e[cnt].x=j,e[cnt].y=i,e[cnt].z=a[i]^a[j];
        }
    }
    sort(e+1,e+cnt+1);
    for(int dx,dy,i=1;i<=cnt;++i)
    {
        dx=find(e[i].x),dy=find(e[i].y);
        if(dx==dy)continue;
        fa[dx]=dy,ans+=e[i].z;
    }
    cout<<ans;
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注