Codeforces1242CSumBalance——状压+爆搜

This way

题意&＃xff1a;

给你k个数组&＃xff0c;每个数组有ni个数&＃xff0c;每个数只会出现一次。现在要将每一个数组中拿出一个数放到任意一个数组中&＃xff0c;并且使得每个数组的数量保持不变。问你每个数组要拿出去的数以及放到哪个数组中

题解&＃xff1a;

我是想用状压dp做来着。。但是那样子要保存每个环的信息所以太麻烦了
那么由于每个数只会出现一次&＃xff0c;所以对于每个数组的每个数拿出去之后&＃xff0c;都会有一个唯一的数补上来。所以我们dfs当前在那个数组以及当前取的环包含的状态&＃xff0c;如果当前行不在状态中&＃xff0c;那么枚举当前行包含的每一个数&＃xff0c;查看取出这个数所能找到的环&＃xff0c;继续向下搜

#include
using namespace std;
#define ll long long
const int N&＃61;5e4&＃43;5;
int n[16],a2[16],k;
ll a[16][N],sum[16],ave,a1[16];
unordered_mapmp;
unordered_mapvis;
int finds(int x,ll val,int s){int now&＃61;x;ll v&＃61;val;s|&＃61;(1<}
void dfs(int x,int s){if(x>k){printf("Yes\n");for(int i&＃61;1;i<&＃61;k;i&＃43;&＃43;)printf("%lld %d\n",a1[i],a2[i]);exit(0);}if(vis[s])return ;if(s&(1<}
int main()
{scanf("%d",&k);for(int i&＃61;1;i<&＃61;k;i&＃43;&＃43;){scanf("%d",&n[i]);for(int j&＃61;1;j<&＃61;n[i];j&＃43;&＃43;){scanf("%lld",&a[i][j]);sum[i]&＃43;&＃61;a[i][j],ave&＃43;&＃61;a[i][j];mp[a[i][j]]&＃61;i;}}if(ave%k)return 0*printf("No\n");ave/&＃61;k;dfs(1,0);printf("No\n");return 0;
}