Codeforces Round 599 (Div. 1+2)___E. Sum Balance —— 子集状压DP

题目链接：点我啊╭(╯^╰)╮

题目大意：

    $k$ 组数，每组数有 $n_i$ 个，所有数互不相同
    从每组数拿出一个放到自己或其他的组
    要求最后每组数的个数与原来的相同
    并且每组数的和相同

解题思路：

    设 $tot$ 为每组数最后的和，则枚举每一组数的每一个值 $a[i][j]$
    若将这个数字拿出，则这组数字需要补上 $tot?sum[i]+a[i][j]$
    也就是从其他组找到上述这个数，补到第 $i$ 组
    若将 $a[i][j]$ 与 $tot?sum[i]+a[i][j]$ 连边，代表需要补上的值
    由于每个数都只出现一次，所以每个数的出度都为1
    所以枚举 $a[i][j]$，根据其出度 $tot?sum[i]+a[i][j]$，可以找到其对应的组
    若 $a[i][j]$ 是个可行值，则由 $a[i][j]$ 出发连的边，最后形成一个环，回到 $a[i][j]$
    也就是最后一个数拿出后要补上 $a[i][j]$
    这个过程由于环上的点的出度都是一定的，所以环上的点可以只访问一次
    时间复杂度$O：(\sum n)$

    在上述枚举 $a[i][j]$ 的过程时，设 $s$ 为处理完的组的状态
    $f[s]$ 记录 $s$ 这个状态，环上所有点的组编号与出度点
    那么最后要求出 $f[(1<<k)?1]$ 的答案
    这个过程可以用子集$DP$，对于一个状态 $s$
    枚举 $s$ 的所有子集 $i$，若 $i$ 可行，且 $s?i$ 可行
    则 $s$ 的状态可以由 $i$ 与 $s?i$ 表示

    枚举一个状态 $s：C_k^i$，其子集的个数为 $C_i^0+C_i^1+C_i^2+...+C_i^i=2^i$
    时间复杂度：$O(C_k^0\times 2^0+C_k^1\times 2^1+C_k^2\times 2^2+...+C_k^k\times 2^k)$
    上式 $=O(C_k^0\times 2^0\times 1^k+C_k^1\times 2^1\times 1^{k?1}+C_k^2\times 2^2\times 1^{k?2}+...+C_k^k\times 2^k\times 1^0)=（1+2{）}^k$

     总时间复杂度：$O(\sum n+3^k)$

核心：子集DP

PS：这里由于 $k$ 值不大，不标记环上的点复杂度为 $O(k\sum n+3^k)$，不大影响

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
using pii = pair <ll,ll>;
const int maxn = 5e3 + 5;
int k, a[16][maxn], cnt[16];
ll sum[16], tot;
unordered_map <ll, ll> mp1, mp2;
vector <pii> f[1<<16], tmp, ans[16];int main() {scanf("%d", &k);for(int i=1; i<=k; i++){scanf("%d", cnt+i);for(int j=1; j<=cnt[i]; j++){scanf("%d", &a[i][j]);sum[i] += a[i][j];mp1[a[i][j]] = i;}tot += sum[i];}if(tot % k) {puts("No");return 0;}tot /= k;for(int i=1; i<=k; i++)for(int j=1; j<=cnt[i]; j++)if(mp1[ tot-sum[i]+a[i][j] ]) mp2[a[i][j]] = tot-sum[i]+a[i][j];else mp2[a[i][j]] = 9e9;for(int i=1; i<=k; i++)for(int j=1; j<=cnt[i]; j++){ll s = 1 << (i - 1), x = mp2[a[i][j]];tmp.clear(); tmp.push_back({i, x});while(x!=9e9 && !(s&(1<<mp1[x]-1)))s |= (1<<mp1[x]-1), tmp.push_back({mp1[x], mp2[x]}), x = mp2[x];if(x == a[i][j] && !f[s].size()) f[s] = tmp;}for(int msk=0; msk<1<<k; msk++){if(f[msk].size()) continue;for(int i=msk; i; i=(i-1)&msk)if(f[i].size() && f[i^msk].size()){for(auto j : f[i]) f[msk].push_back(j);for(auto j : f[i^msk]) f[msk].push_back(j);break;}}if(!f[(1<<k)-1].size()) {puts("No");return 0;}puts("Yes");for(auto i : f[(1<<k)-1]) ans[mp1[ i.second ]].push_back(i);for(int i=1; i<=k; i++) printf("%lld %lld\n", ans[i][0].second, ans[i][0].first);
}