最大权闭合图，CF 2026E - Best Subsequence

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

二、解题报告

1、思路分析

如果一个数被选了，那么它所有为1的二进制位也得被选

这符合我们对于闭合图的定义，那么这道题就是一个最小割问题了

关于最小割：

我们这样建模：

数字和二进制位都看成带权节点，根据题目对于value的定义，一个被选的数字贡献1，一个二进制位贡献-1，那么我们按照闭合图网络流建模的方式：

源点向每个数字连 容量为1 的边

0~60的每个二进制位向汇点连 容量为1 的边

每个数字向它是1的二进制位连容量为正无穷的边

那么 价值就是闭合图的点权

最大闭合图点权就是 正权和 - 最小割

2、复杂度

时间复杂度： O(NM^2)空间复杂度：O(N + M)，这里M 约等于 60N

3、代码详解

 ​

#include <bits/stdc++.h>

// #define DEBUG

using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;

constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;

template<class T>
struct MaxFlow{
    struct Edge{
        int v;
        T cap;
        Edge(int _v, T _cap): v(_v), cap(_cap) {}
    };

    int n;
    std::vector<Edge> e;
    std::vector<std::vector<int>> g;
    std::vector<int> cur, h;
    
    MaxFlow() {}
    MaxFlow(int _n) {
        init(_n);
    }

    void init(int _n) {
        n = _n;
        e.clear();
        g.assign(n, {});
        cur.resize(n);
        h.resize(n);
    }

    bool bfs(int s, int t) {
        h.assign(n, -1);
        std::queue<int> q;
        h[s] = 0;
        q.push(s);
        while (q.size()) {
            const int u = q.front();
            q.pop();
            for (int i : g[u]) {
                auto [v, c] = e[i];
                if (c > 0 && h[v] == -1) {
                    h[v] = h[u] + 1;
                    if (v == t) return true;
                    q.push(v);
                }
            }
        }
        return false;
    }

    T dfs(int u, int t, T f) {
        if (u == t) return f;
        auto r = f;
        for (int &i = cur[u]; i < (int)g[u].size(); ++ i) {
            const int j = g[u][i];
            auto [v, c] = e[j];
            if (c > 0 && h[v] == h[u] + 1) {
                auto a = dfs(v, t, std::min(r, c));
                e[j].cap -= a;
                e[j ^ 1].cap += a;
                r -= a;
                if (r == 0) return f;
            }
        }
        return f - r;
    }

    void addEdge(int u, int v, T c) {
        g[u].push_back(e.size());
        e.emplace_back(v, c);
        g[v].push_back(e.size());
        e.emplace_back(u, 0);
    }

    T flow(int s, int t) {
        T ans = 0;
        while (bfs(s, t)) {
            cur.assign(n, 0);
            ans += dfs(s, t, std::numeric_limits<T>::max());
        }
        return ans;
    }

    std::vector<bool> minCut() {
        std::vector<bool> c(n);
        for (int i = 0; i < n; ++ i)
            c[i] = (h[i] != -1);
        return c;
    }

    struct _Edge{
        int u;
        int v;
        T cap;
        T flow;
    };
    std::vector<_Edge> edges() {
        std::vector<int> a;
        for (int i = 0; i < e.size(); i += 2) {
            Edge x;
            x.u = e[i + 1].v;
            x.v = e[i].v;
            x.cap = e[i].cap + e[i + 1].cap;
            x.flow = e[i + 1].cap;
            a.push_back(x);
        }
        return a;
    }
};

void solve() {
    int n;
    std::cin >> n;

    std::vector<i64> a(n);
    for (int i = 0; i < n; ++ i) {
        std::cin >> a[i];
    }

    MaxFlow<int> g(n + 62);

    int s = n + 60, t = s + 1;

    for (int i = 0; i < n; ++ i) {
        g.addEdge(s, i, 1);

        for (int j = 0; j < 60; ++ j) {
            if (a[i] >> j & 1){
                g.addEdge(i, n + j, inf32);
            }
        }
    }

    for (int i = 0; i < 60; ++ i){ 
        g.addEdge(n + i, t, 1);
    }

    std::cout << n - g.flow(s, t) << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

#ifdef DEBUG
    int START = clock();
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif

    int t = 1;
    std::cin >> t;

    while (t --) {
        solve();
    }
#ifdef DEBUG
    std::cerr << "run-time: " << clock() - START << '\n';
#endif
    return 0;
}