UOJ 176 新年的繁荣

挺妙的解法。

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

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

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

Code：

1#include <cstdio>
2#include <cstring>
3using namespace std;
4typedef long long ll;
5
6const int N = 18;
7
8int n, m, a[1 << N], ufs[1 << N];
9ll ans = 0LL;
10
11inline void read(int &X) {
12    X = 0; char ch = 0; int op = 1;
13    for(; ch > '9' || ch < '0'; ch = getchar())
14        if(ch == '-') op = -1;
15    for(; ch >= '0' && ch <= '9'; ch = getchar())
16        X = (X << 3) + (X << 1) + ch - 48;
17    X *= op; 
18}
19
20inline int find(int x) {
21    return ufs[x] == x ? x : ufs[x] = find(ufs[x]);
22}
23
24inline bool merge(int x, int y) {
25    int fx = find(x), fy = find(y);
26    if(fx == fy) return 0;
27    ufs[fx] = fy;
28    return 1;
29}
30
31int main() {
32//    freopen("Sample.txt", "r", stdin);
33    
34    read(n), read(m);
35    for(int x, i = 1; i <= n; i++) {
36        read(x);
37        if(a[x]) ans += 1LL * x;
38        else a[x] = x;
39    }
40    
41    for(int i = 1; i < (1 << m); i++) ufs[i] = i;
42    for(int i = (1 << m) - 1; i >= 0; i--) {
43        for(int j = 0; j < m && (!a[i]); j++)
44            a[i] = a[i | (1 << j)];
45        for(int j = 0; j < m; j++)
46            if(a[i | (1 << j)] && merge(a[i], a[i | (1 << j)]))
47                ans += 1LL * i;
48    }
49    
50    printf("%lld\n", ans);
51    return 0;
52}

View Code