2025传智杯复赛第二场官方题解 | T8 | #选择队伍(hard)#

题意

给定 $4n$ 名学生，均分为 $a, b, c, d$ 四组。两名学生 $i, j$ 的默契值为 $f(i, j) = (i \oplus j) + (i \mid j) + (i \,\&\, j)$ 。

$\hspace{15pt}$ 要求组建 $m$ 支队伍（每队由四组各出一人，按题意为队伍结构为 $B \to A \to C \to D$ 的链式匹配），使得每名学生最多被选中一次的前提下，总默契值最大。

题解

首先考察默契值的计算公式，根据基本的位运算性质： $i + j = (i \oplus j) + 2(i \,\&\, j)$ ，同时 $i \mid j = (i \oplus j) + (i \,\&\, j)$ 。将这两个性质代入原式化简，可以得到一个非常简洁的结果： $f(i, j) = 2 \times (i \mid j)$

这意味着单支队伍（设成员分别为 $a_i, b_j, c_k, d_l$ ）的默契值总和为 $2(b_j \mid a_i) + 2(a_i \mid c_k) + 2(c_k \mid d_l)$ 。我们需要从四组中挑选出 $m$ 条不相交的成员链，并最大化这 $m$ 条链的权值之和。

既然涉及多部图的匹配以及最大化权值问题，而且每个节点有严格的使用次数限制，很自然地可以转化为**最小费用最大流（MCMF）**模型解决。只需将所有边权取相反数，求最小费用即可等价于最大化收益。

具体建图方式如下：将匹配关系视为网络流中的一条分层路径 $S \to B \to A \to C \to D \to T$ 。为保证处于端点的 $B$ 组和 $D$ 组每人只被分配一次，从源点 $S$ 向 $B$ 组各点连容量为 $1$ 、费用为 $0$ 的边，并从 $D$ 组各点向汇点 $T$ 连容量为 $1$ 、费用为 $0$ 的边。对于处于路径中间节点的 $A$ 组和 $C$ 组学生，直接连边无法限制其被重复选中，因此需要对这两组的节点进行拆点——将每个点拆分为“入点”和“出点”，两点之间连一条容量为 $1$ 、费用为 $0$ 的内部边。组别与组别之间的匹配，则直接按链的顺序进行跨层连边，容量均为 $1$ ，费用为 $-2(x \mid y)$ 。

完成建图后，只要在这个网络上限制总流量为 $m$ 跑最小费用最大流，跑出的最小费用的相反数即为答案。

在算法的具体实现上，由于初始网络中存在负权边，最普遍的做法是使用基于 SPFA 的费用流。由于本题数据范围较小（ $n, m \le 100$ ），且单纯的分层图结构极难构造出能卡掉 SPFA 的极端数据，因此常规做法就能顺利通过。

如果追求更严谨的时间复杂度，可以使用 Primal-Dual（原始对偶） 算法进行优化。观察到初始残量网络是一个完美的有向无环图（DAG），所有边都严格从前一层指向后一层。因此，在第一次寻找增广路前，可以直接利用 DAG 的性质，通过 $O(V+E)$ 的拓扑排序动态规划求出起点到各点的最短路，将其作为节点的初始势能 $h$ 。引入势能后，所有的边权均被等效转化为非负权，后续所有的增广寻找最短路环节都可以使用基于优先队列的 Dijkstra 算法完成，从而彻底规避了 SPFA 在最坏情况下的退化风险，具有极佳的稳定性。

复杂度

时间复杂度: $\mathcal{O}(m \cdot E \log V)$ ，代入点数 $V \approx 6n$ 和边数 $E \approx 3n^2$ ，约为 $\mathcal{O}(m \cdot n^2 \log n)$ 。
空间复杂度: $\mathcal{O}(n^2)$

参考代码

cpp1
cpp2

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

template<typename T> class CostFlow {
  public:
    const int n;
    static constexpr T inf = numeric_limits<T>::max();
    T flow, cost;

    vector<tuple<int, T, T>> e;
    vector<vector<int>> g;
    vector<T> d;
    vector<bool> vis;

    struct Edge {
        int from;
        int to;
        T cap;
        T cost;
        T flow;
    };

    CostFlow(int n) : n(n), g(n), vis(n) {}

    constexpr void addedge(int u, int v, T c, T w = 0) {
        g[u].push_back(e.size());
        e.emplace_back(v, c, w);
        g[v].push_back(e.size());
        e.emplace_back(u, 0, -w);
    }

    constexpr bool spfa(int s, int t) {
        d.assign(n, inf);
        d[t] = 0;
        vis.assign(n, false);
        vis[t] = true;
        deque<int> q;
        q.push_back(t);

        while (!q.empty()) {
            auto u = q.front();
            q.pop_front();
            vis[u] = false;
            for (int i : g[u]) {
                auto &[v, c, w] = e[i];
                auto &[_, rc, __] = e[i ^ 1];
                if (rc && d[v] > d[u] - w) {
                    d[v] = d[u] - w;
                    if (!vis[v]) {
                        vis[v] = true;
                        if (!q.empty() && d[v] < d[q.front()]) {
                            q.push_front(v);
                        } else {
                            q.push_back(v);
                        }
                    }
                }
            }
        }
        return d[s] != inf;
    }

    constexpr T dfs(int u, int t, T f) {
        vis[u] = true;
        if (u == t) {
            return f;
        }
        auto r = f;
        for (int i : g[u]) {
            auto &[v, c, w] = e[i];
            auto &[_, rc, __] = e[i ^ 1];
            if (!vis[v] && c && d[u] - w == d[v]) {
                auto a = dfs(v, t, min(r, c));
                if (a) {
                    cost += a * w;
                    c -= a;
                    rc += a;
                    r -= a;
                    if (!r) return f;
                }
            }
        }
        return f - r;
    }

    constexpr vector<Edge> edges() {
        vector<Edge> a;
        for (int i = 0; i < e.size(); i += 2) {
            Edge x;
            x.from = get<0>(e[i + 1]);
            x.to = get<0>(e[i]);
            x.cap = get<1>(e[i]) + get<1>(e[i + 1]);
            x.cost = get<2>(e[i]);
            x.flow = get<1>(e[i + 1]);
            a.push_back(x);
        }
        return a;
    }

    constexpr pair<T, T> costFlow(int s, int t) {
        flow = cost = 0;
        while (spfa(s, t)) {
            vis[t] = true;
            while (vis[t]) {
                vis.assign(n, false);
                flow += dfs(s, t, inf);
            }
        }
        return {flow, cost};
    }
};

auto main() -> signed {
    cin.tie(0), ios::sync_with_stdio(0);
    int n, m;
    cin >> n >> m;

    vector<i64> a(n), b(n), c(n), d(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < n; ++i) cin >> b[i];
    for (int i = 0; i < n; ++i) cin >> c[i];
    for (int i = 0; i < n; ++i) cin >> d[i];

    CostFlow<i64> cf(6 * n + 3);
    for (int i = 1; i <= n; i++) {
        cf.addedge(0, 2 * n + i, 1);
    }

    // S -> b -> a1 -> a2 -> c1 -> c2 -> d -> T
    for (int i = 5 * n + 1; i <= 6 * n; i++) {
        cf.addedge(i, 6 * n + 1, 1);
    }
    cf.addedge(6 * n + 1, 6 * n + 2, m);

    // b -> a1 -> a2
    for (int i = 2 * n + 1; i <= 3 * n; i++) {
        for (int j = 1; j <= n; j++) {
            cf.addedge(i, j, 1, -2 * (b[i - 1 - 2 * n] | a[j - 1]));
        }
    }

    // a2 -> c1 -> c2
    for (int i = n + 1; i <= 2 * n; i++) {
        for (int j = 3 * n + 1; j <= 4 * n; j++) {
            cf.addedge(i, j, 1, -2 * (a[i - 1 - n] | c[j - 1 - 3 * n]));
        }
    }

    // c2 -> d
    for (int i = 4 * n + 1; i <= 5 * n; i++) {
        for (int j = 5 * n + 1; j <= 6 * n; j++) {
            cf.addedge(i, j, 1, -2 * (c[i - 1 - 4 * n] | d[j - 1 - 5 * n]));
        }
    }


    for (int i = 1; i <= n; i++) {
        cf.addedge(i, n + i, 1);
    }

    for (int i = 1; i <= n; i++) {
        cf.addedge(3 * n + i, 4 * n + i, 1);
    }

    auto [flow, cost] = cf.costFlow(0, 6 * n + 2);
    cout << -cost << '\n';
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;
using pii = pair<i64, i64>;
const i64 INF = 1e18;

struct Edge {
    int to;
    int cap;
    i64 cost;
    int rev;
};

int main() {
    int n, m; cin >> n >> m;

    vector<i64> a(n), b(n), c(n), d(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < n; ++i) cin >> b[i];
    for (int i = 0; i < n; ++i) cin >> c[i];
    for (int i = 0; i < n; ++i) cin >> d[i];

    int N = 6 * n + 2;
    int S = 0, T = N - 1;

    vector<vector<Edge>> adj(N);

    auto add_edge = [&](int u, int v, int cap, i64 cost) {
        adj[u].push_back({v, cap, cost, (int)adj[v].size()});
        adj[v].push_back({u, 0, -cost, (int)adj[u].size() - 1});
    };
    for (int i = 0; i < n; ++i) {
        add_edge(S, 1 + i, 1, 0);
        add_edge(1 + n + i, 1 + 2 * n + i, 1, 0);
        add_edge(1 + 3 * n + i, 1 + 4 * n + i, 1, 0);
        add_edge(1 + 5 * n + i, T, 1, 0);
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {            
            // b_i -> a_j
            add_edge(1 + i, 1 + n + j, 1, -2LL * (b[i] | a[j]));

            // a_i -> c_j
            add_edge(1 + 2 * n + i, 1 + 3 * n + j, 1, -2LL * (a[i] | c[j]));

            // c_i -> d_j
            add_edge(1 + 4 * n + i, 1 + 5 * n + j, 1, -2LL * (c[i] | d[j]));
        }
    }

    vector<i64> h(N, INF);
    h[S] = 0;
    for (int u = 0; u < N; ++u) {
        if (h[u] == INF) continue;
        for (auto& e : adj[u]) {
            if (e.cap > 0 && h[e.to] > h[u] + e.cost) {
                h[e.to] = h[u] + e.cost;
            }
        }
    }

    i64 ans = 0;
    for (int step = 0; step < m; ++step) {
        vector<i64> dist(N, INF), p_v(N, -1), p_e(N, -1);
        dist[S] = 0;
        
        priority_queue<pii, vector<pii>, greater<pii>> pq;
        pq.push({0, S});

        while (!pq.empty()) {
            auto [d_u, u] = pq.top();
            pq.pop();
            if (d_u > dist[u]) continue;
            for (int i = 0; i < adj[u].size(); ++i) {
                auto& e = adj[u][i];
                if (e.cap > 0 && dist[e.to] > dist[u] + e.cost + h[u] - h[e.to]) {
                    dist[e.to] = dist[u] + e.cost + h[u] - h[e.to];
                    p_v[e.to] = u;
                    p_e[e.to] = i;
                    pq.push({dist[e.to], e.to});
                }
            }
        }

        for (int i = 0; i < N; ++i) {
            if (dist[i] != INF) {
                h[i] += dist[i];
            }
        }

        int push = 1, curr = T;
        while (curr != S) {
            int u = p_v[curr];
            int idx = p_e[curr];
            adj[u][idx].cap -= push;
            adj[curr][adj[u][idx].rev].cap += push;
            curr = u;
        }

        ans += h[T];
    }

    cout << -ans << (char)(10);

    return 0;
}

int __OI_INIT__ = []() {
    ios::sync_with_stdio(0), cin.tie(0);
    cout.tie(0);
    cout << fixed << setprecision(12);
    return 0;
}();