本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-05-02 21:39:39

题解思路：

无解情况：

所有的价值和不是 $k$ 的倍数那么他就无解。

我们发现每个合法都是一个环。

那么我们就可以用二进制表示。

然后我们就看这些二进制能否构成全一串就可以了。

具体怎么做：

首先判断是否有解，即他们的价值和 $\mod k = 0$。

预处理环。

状压 dp $\longrightarrow$ 二进制全 $1$。

AC CODE:

#include <cstring>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
ll sum[15];
vector <int> a[15];
map <ll , pair <int , int>> mp;
bool vis[1 << 15] , dp[1 << 15];
vector <pair <pair<int , int> , int>> mark[1 << 15];
int pre[1 << 15];
pair <int , int> ans[15];
int main() {
    int k;
    scanf ("%d" , &k);
    ll v = 0;
    for (int i = 0; i < k; ++ i) {
        int n;
        scanf ("%d" , &n);
        a[i].resize (n);
        for (int j = 0; j < n; ++ j) {
            scanf ("%d" , &a[i][j]);
            sum[i] += a[i][j];\/\/sum[i]第i组的和
            mp[a[i][j]] = {i , j};\/\/i组j个
        }
        v += sum[i];\/\/总和 
    }
    if (v % k != 0) return puts("No") , 0;\/\/无解
    v \/= k;\/\/分成k个小段，每段的和
    for (int i = 0; i < k; ++ i) {\/\/预处理环
        for (int j = 0; j < a[i].size(); ++ j) {
            ll cur = a[i][j];\/\/枚举a[i][j]，复杂度15×5000
            int now = 0;\/\/现在的状态
            bool ok = true;
            vector <pair<pair <int , int> , int>>b;
            while (1) {
                int y = mp[cur].first;\/\/用map记录
                cur = v - sum[y] + cur;\/\/他对应的值：sum[i]+a[i][j]+?=v,我们已知：sum[i],v,
                if (!mp.count(cur)) {
                    ok = false;
                    break;
                }
                auto x = mp[cur];
                if (now & (1 << x.first)) {
                    ok = false;
                    break;
                }
                now |= (1 << x.first);
                b.push_back ({{x.first , x.second} , y});
                if (x.first == i) {\/\/一直往前找，又回到了期点，有环
                    if (x.second != j) ok = false;
                    break;
                }
            }
            if (ok) {
                vis[now] = true;
                mark[now] = b;
            }
        }
    }
    dp[0] = 1;
    for (int s = 0; s < (1 << k); ++ s) {\/\/枚举子集，状压DP
        for (int ns = s; ns; ns = (ns - 1) & s)
            if (vis[ns] && dp[s ^ ns]) {
                dp[s] = 1;
                pre[s] = ns;
                break;
            }
    }
    if (!dp[(1 << k) - 1]) return puts("No") , 0;\/\/没有全1那么也无解
    int s = 1 << k;
    -- s;
    while (s) {
        for (auto &x : mark[pre[s]]) {
            ans[x.first.first] = {a[x.first.first][x.first.second] , x.second};
        }
        s ^= pre[s];
    }
    puts("Yes");
    for (int i = 0; i < k; ++ i)
        printf ("%d %d\n" , ans[i].first , ans[i].second + 1);
    return 0;
}

码字不易，求赞！