UOJ 176 新年的繁荣

挺妙的解法。

发现边权很小，我们可以考虑从大到小枚举边权来进行$kruskal$算法，这样子对于每一个边权$i$，我们只要枚举$0 \leq j < m$，找到一个点使它的点权为$i | 2^j$，尝试连边即可。

另外，如果同一个点权重复出现，一定有办法使这个边权连满，这样子直接累加到答案里就可以了。

时间复杂度$O(m * 2^m)$，再套一个并查集的复杂度。

Code：

#include <cstdio>

#include <cstring>

using namespace std;

typedef long long ll;

const int N = ;

int n, m, a[ << N], ufs[ << N];

ll ans = 0LL;

inline void read(int &X) {

    X = ; char ch = ; int op = ;

    for(; ch > '' || ch < ''; ch = getchar())

        if(ch == '-') op = -;

    for(; ch >= '' && ch <= ''; ch = getchar())

        X = (X << ) + (X << ) + ch - ;

    X *= op;

}

inline int find(int x) {

    return ufs[x] == x ? x : ufs[x] = find(ufs[x]);

}

inline bool merge(int x, int y) {

    int fx = find(x), fy = find(y);

    if(fx == fy) return ;

    ufs[fx] = fy;

    return ;

}

int main() {

//    freopen("Sample.txt", "r", stdin);

    read(n), read(m);

    for(int x, i = ; i <= n; i++) {

        read(x);

        if(a[x]) ans += 1LL * x;

        else a[x] = x;

    }

    for(int i = ; i < ( << m); i++) ufs[i] = i;

    for(int i = ( << m) - ; i >= ; i--) {

        for(int j = ; j < m && (!a[i]); j++)

            a[i] = a[i | ( << j)];

        for(int j = ; j < m; j++)

            if(a[i | ( << j)] && merge(a[i], a[i | ( << j)]))

                ans += 1LL * i;

    }

    printf("%lld\n", ans);

    return ;

}