Liveddd's Blog

愛にできることはまだあるかい

CF1305G Kuroni and Antihype

发表于 更新于 分类于
本文字数： 3.1k 阅读时长 ≈ 7 分钟

不错的图论题。

考虑转化。最优情况下，答案构成的图形如森林。且重要的一点，一个点对答案的贡献与该点度数相关。

添加一个点权为 $0$ 的点 $n+1$，并其它点连边，这一步相当于将森林转化为树，并且计算原森林中根节点的贡献（因为实际上贡献是 $0$，需要特殊处理）。并且设图中边 $(u,v)$ 的边权为 $a_u+a_v$。答案为其最大生成树减去 $\sum a_i$。

问题直接变为如何快速求最大生成树。注意到一个经典性质 $a+b=a| b+a\& b$，已知 $a_u \& a_v=0$，于是尝试直接枚举边权 $w$，再枚举其子集中得到点 $u$，连边 $(u,v=w\oplus u)$ 即可。时间复杂度为 $\mathcal O(3^{\log_2 V})=\mathcal O(V^{\log_2 3})$。可以通过。

考虑更优的做法。相当于求 $a_u$ 的补集的子集中最优的。这一步显然可以用 FMT 做。这样我们每次对于每个点都能够找到最优的一条边，这正是 Boruvka 所需要的。我们在 Boruvka 的过程中 做 FMT 即可，注意需要记录次大值及其编号。时间复杂度为 $\mathcal O(V\log V\log n )$。

Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<iostream>
#include<cstdio>
#include<cstring>
#define fi first 
#define se second
using namespace std;
using PII=pair<int,int>;
using ll=long long;
const int M=18,N=(1<<M)+10;
template <class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=-x;
}
template <class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
struct Node
{
    PII x,y;
    void operator+=(const PII &t)
    {
        if(t.fi>x.fi||(t.fi==x.fi&&t.se!=x.se))
        {
            if(t.se!=x.se)y=x;
            x=t;
        }
        else if(t.fi>y.fi&&t.se!=x.se)y=t;
    }
    void operator+=(const Node &t)
    {
        *this+=t.x,*this+=t.y;
    }
}f[N];
PII g[N];
int n,bit,all;
ll ans;
int a[N];
int fa[N];
int get(int x){return x==fa[x]?x:fa[x]=get(fa[x]);}
inline bool merge(int x,int y)
{
    x=get(x),y=get(y);
    if(x==y)return 0;
    fa[x]=y;
    return 1;
}
int main()
{
    read(n);
    for(int i=1;i<=n;i++)read(a[i]),ans-=a[i],all=max(all,a[i]);
    n++;
    for(int i=1;i<=n;i++)fa[i]=i;
    for(;all;all>>=1)bit++;
    all=1<<bit;
    int cnt=n;
    while(cnt>1)
    {
        for(int i=0;i<all;i++)f[i].x=f[i].y={-1,-1};
        for(int i=1;i<=n;i++)g[i]={-1,-1};
        for(int i=1;i<=n;i++)f[a[i]]+={a[i],get(i)};
        for(int i=0;i<bit;i++)
            for(int j=0;j<all;j++)
                if(j>>i&1)
                    f[j]+=f[j^(1<<i)];
        for(int i=1;i<=n;i++)
        {
            Node res=f[(all-1)^a[i]];
            int x=get(i);
            if(res.x.fi==-1)continue;
            if((res.x.fi^a[i])>g[x].fi&&res.x.se!=x)
                g[x]=res.x,g[x].fi^=a[i];
            if(res.y.fi==-1)continue;
            if((res.y.fi^a[i])>g[x].fi&&res.y.se!=x)
                g[x]=res.y,g[x].fi^=a[i];
        }
        for(int i=1;i<=n;i++)
            if(get(i)==i&&g[i].fi!=-1&&merge(g[i].se,i))
                cnt--,ans+=g[i].fi;
    }
    printf("%lld\n",ans);
    return 0;
}