CF1243E 题解（图论，状压dp）

首先，所有box的sum必须被 $k$ 整除，否则无解。

令 $tar$ 为最终每个box的sum。

我们可以枚举 $box ~1$ 要拿哪个数出来（叫做 $a_1$），这样我们就可以知道它需要被放入哪个数（叫做 $b_1$）。又因为所有数字都不相同，故我们就可以知道 $b_1$ 的来源是哪个box，假设来自 $box_i$，那么我们就可以得到 $a_i = b_1$，于是就可以计算出 $b_i$，一直这么继续下去。

如果最终形成了一个 完整环（以 $box_1$ 作为起点，并且以 $box_1$ 作为终点）的话，就说明这个方案可行。

但是，这个环不一定覆盖了所有的点。所以我们需要找到所有的环，我们分别以 $1,2,3,…,k$ 作为起点，并且对于每个box都枚举一下要拿的数。这样我们可以最多形成 $\sum\limits_{i=1}^k n_i \leq 75000$ 个环。并且每个环一定互不相同。

现在的问题就转化为：给定了这些环，我们能否从中挑选出几个环，使得每个 $box$ 被访问，且仅被访问一次？

用 Bitmask ！

因为 $k \leq 15$，我们将每个环表示为一个bitmask，比如某个环是 $1 \rightarrow 2 \rightarrow 4 \rightarrow 1$，那么对应的bitmask就是 $000…1011$。

我们会发现，可能会有很多个环对应同一个bitmask，但是没关系，我们只需要输出一个解即可。

最后，问题转化为：给定一些bitmask，如何让它们组合成 $2^k-1$，且每个bit仅被覆盖一次？

用 状压dp！

定义 bool ori[(1<<16)+2], dp[(1<<16)+2];

其中 ori[mask] 代表这个mask是否由 单独一个环 所组成，而 dp[mask] 代表这个mask能否由 $1$ 个 或多个环 组成。

然后就是一个很经典的模版了：

for (int mask = 0; mask <= (1<<k)-1; mask++) {
    if (ori[mask]) {
        dp[mask] = 1;
        continue;
    }
    for (int sub = mask; sub; sub = (sub-1) & mask) {   // 枚举mask的子集，使用 (sub-1) & mask来加速枚举
        if (dp[sub] && dp[mask ^ sub]) {  // 使用xor保证同一个bit只被覆盖一次
            dp[mask] = 1;
            break;
        }
    }
}

最后就是实现了，本题实现起来相当麻烦，找 完整环 用的是 $dfs$ + $bitmask$ + 记录起点（和起点使用的数），每次找到一个环，就把 起点 放在对应的 $bitmask$ 数组 plan[] 里。

在找完所有的环之后，再根据每个 $bitmask$，再进行一次 $dfs$ 来找到这个环的具体路径。

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

#define ll long long
#define pii pair<int,int>

int k;
int adj[16][5002];  //记录第i个box的第j个数
int sz[16];  //记录第i个box的大小
ll sum[16];
ll diff[16];  // 记录第i个box的sum和target的差
unordered_map<ll, int> belong;  // 记录某个数属于第几个box

pii plan[(1<<16)+2];  // 储存每个bitmask对应的起点 {start, a}
bool ori[(1<<16)+2];
bool dp[(1<<16)+2];
int from[(1<<16)+2];  // 记录每个bitmask在dp过程中由哪个子集转移过来的
pii ans[16];

void dfs(int cur, ll a, int mask, int start, ll oa) {  //cur: current vertex, a: the number we are taking OUT from cur, start: the starting vertex, oa: the "a" for starting vertex
    ll need = a - diff[cur];

    if (!belong.count(need)) return;  // no vertex to go
    int to = belong[need];
    mask |= (1<<(cur-1));
    if (to == start && need == oa) {
        ori[mask] = 1;
        plan[mask] = {start, oa};
        return;
    }

    if (mask & (1<<(to-1))) return;  // form a cycle, but not a cycle start with "start"
    dfs(to, need, mask, start, oa);
}

void dfs2(int cur, ll a, int mask, int start) {
    ll need = a - diff[cur];
    int to = belong[need];
    mask |= (1<<(cur-1));
    ans[to] = {need, cur};
    if (to == start) {
        return;
    }

    dfs2(to, need, mask, start);
}

void findans(int mask) {
    if (!ori[mask]) {
        findans(from[mask]);
        findans(from[mask] ^ mask);
        return;
    }

    int start = plan[mask].first;
    ll a = plan[mask].second;
    dfs2(start, a, 0, start);
}


int main() {
    cin >> k;
    for (int i = 1; i <= k; i++) {
        int n; cin >> n;
        sz[i] = n;
        for (int j = 1; j <= n; j++) {
            ll a; cin >> a;
            adj[i][j] = a;
            sum[i] += a;
            belong[a] = i;
        }
    }
    ll tar = 0;
    for (int i = 1; i <= k; i++) tar += sum[i];
    if (tar % k) {
        cout << "No" << endl;
        return 0;
    }
    tar = tar/k;
    for (int i = 1; i <= k; i++) {
        diff[i] = sum[i] - tar;
    }

    for (int start = 1; start <= k; start++) {
        for (int j = 1; j <= sz[start]; j++) {
            dfs(start, (ll)adj[start][j], 0, start, adj[start][j]);
        }
    }

    for (int mask = 0; mask <= (1<<k)-1; mask++) {
        if (ori[mask]) {
            dp[mask] = 1;
            continue;
        }
        for (int sub = mask; sub; sub = (sub-1) & mask) {
            if (dp[sub] && dp[mask ^ sub]) {
                dp[mask] = 1;
                from[mask] = sub;
                break;
            }
        }
    }

    if (dp[(1<<k)-1]) {
        cout << "Yes" << "\n";
        findans((1<<k)-1);
        for (int i = 1; i <= k; i++) printf("%d %d\n", ans[i].first, ans[i].second);
    } else {
        cout << "No" << "\n";
    }
}