#状压dp，拓扑排序，内向基环树#CF1242C Sum Balance

题目

有 \(k\) 个盒子, 第 \(i\) 个盒子有 \(n_i\) 个数. 保证所有数互不相同。

从每个盒子各拿出一个数, 并按照某种顺序放回去(每个盒子恰好放入一个数)。

判断是否能使操作后所有盒子内的数的和相同, 有解需要输出任意一个方案。

\(k\leq 15,n_i\leq 5000\)

分析

可以发现拿出一个数，那么放进去的这个数也是确定的，那么这样就确定的有向的关系。

由于每个点只往外连一条边，所以这张有向图实则形成一个内向基环树。

相当于要将所有的环抽出来，可以作为一种子方案，然后再将所有环拼接起来，相当于枚举子集。

时间复杂度为 \(O(3^k+2^k*k)\)

可以先跑一遍拓扑排序将非环的部分剔除掉，然后只找环的部分，注意如果环内存在两个数在同一盒子且并不相同，那么这个环不能使用。

代码

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int N=80101; vectorans[N]; mapdfn; queueq;
int xo[N],deg[N],nxt[N],v[N],n,al,a[16][N>>4],S,tot,X[N],Y[N],pre[N]; long long s[16],sum;
int iut(){
	int ans=0,f=1; char c=getchar();
	while (!isdigit(c)) f=(c=='-')?-f:f,c=getchar();
	while (isdigit(c)) ans=ans*10+c-48,c=getchar();
	return ans*f;
}
int main(){
	n=iut(),al=(1<>(X[x]-1))&1) flag=0;
		    pre[nxt[x]]=x,v[x]=1,S|=1<<(X[x]-1);
		}
		if (!flag||!ans[S].empty()) continue;
		ans[S].push_back(i);
		for (int x=nxt[i];x!=i;x=nxt[x]) ans[S].push_back(x);
	}
	for (int i=1;i<=al;++i)
	if (ans[i].empty()){
		for (int j=i&(i-1);j;j=(j-1)&i)
		if (!ans[j].empty()&&!ans[i^j].empty()){
			ans[i]=ans[i^j];
			for (int k=0;k
DP-线性、区间、树形、状压dp图论-直径、重心、基环树

相关

标签