CF1519F Chests and Keys 做题记录

给定 $n,m$ 表示存在 $n$ 个宝箱和 $m$ 把钥匙，第 $i$ 把钥匙需要 $b_i$ 元，第 $i$ 个宝箱内部有 $a_i$ 元。

现在进行一场游戏，Bob 是本场游戏的玩家，而 Alice 则是场景布置者，Alice 可以给每个宝箱上一些锁（第 $j$ 种锁需要第 $j$ 种钥匙打开）

如果 Bob 可以购买一些钥匙，然后打开一些宝箱，使得 Bob 的收益大于 $0$，那么 Bob 就赢得了游戏，反之 Alice 获得了胜利。

现在 Alice 打算布置宝箱上的锁，第 $i$ 个宝箱上放置第 $j$ 种锁的花费为 $c_{i,j}$，请帮助 Alice 找到一种布置锁的方案，使得花费最小，且 Alice 将取得胜利。

注意：一个箱子上可以放置若干把锁，Bob 需打开所有锁才能获得内部的钱。

$n,m\le 6,a_i,b_i\le 4,c_{i,j}\le 10^7$。

设箱子 $i$ 上的锁的集合为 $L_i$，那么 $L$ 需要满足：

$\forall S\subseteq\{1,2,3,\dots n\},\sum\limits_{u\in S} a_u\le \sum\limits_{v\in (\cup_{u\in S}L_u)}b_v$

注意到这个东西很像 Hall 定理，那么考虑建立一张这样的二分图：

• 左部每个箱子拆成 $a_i$ 个点，共有 $\sum\limits_{i=1}^n a_i$ 个点；
• 右部每个锁拆成 $b_i$ 个点，共有 $\sum\limits_{i=1}^m b_i$ 个点；
• 若 $i$ 号箱子有 $j$ 号锁，那么从 $i$ 号箱子拆出的所有点和 $j$ 号锁拆出的所有点之间连一条边；

问题等价于最小化有连边的锁的 $b_i$ 和，使得二分图存在大小为 $\sum\limits_{i=1}^n a_i$ 的匹配。

那么直接找大小为 $\sum\limits_{i=1}^n a_i$ 的匹配即可。设 $dp_{i,st}$ 为前 $i$ 个箱子拆出来的点都匹配完了，锁拆出来的点的状态为 $st$（五进制，每个锁拆出来的点还有多少个）时的最小代价。那么转移直接枚举当前箱子拆出来的每个点匹配了哪个锁拆成的点，如果匹配了至少一个锁 $j$ 拆出来的点，则需要加上 $c_{i,j}$ 的代价。

时间复杂度 $O(nm2^{2n})$，跑不满所以能过。

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int S=8,SS=45,BS=20005;

int n,m;
int a[S],b[S],c[S][S];
int tot[SS],sta[SS][BS][S];
int st[S],pst[S];
int dp[S][BS];

inline int getval()
{
	int val=0;
	for(int i=1;i<=m;i++)
	{
		val*=5;
		val+=st[i];
	}
	return val;
}

inline void getsta(int val)
{
	for(int i=m;i>=1;i--)
	{
		st[i]=val%5;
		val/=5;
	}
}

inline void tmin(int &x,int y)
{
	x=min(x,y);
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=m;i++) scanf("%d",&b[i]);
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&c[i][j]);
	for(int i=1;i<=m;i++) st[i]=b[i];
	int mxval=getval();
	for(int i=0;i<=mxval;i++)
	{
		getsta(i);
		int cnt=0;
		for(int j=1;j<=m;j++) cnt+=st[j];
		tot[cnt]++;
		for(int j=1;j<=m;j++) sta[cnt][tot[cnt]][j]=st[j];
	}
	memset(dp,127,sizeof(dp));
	int inf=dp[0][0];
	dp[0][mxval]=0;
	for(int i=0;i<=n-1;i++)
	{
		for(int j=0;j<=mxval;j++)
		{
			if(dp[i][j]==inf) continue;
			getsta(j);
			for(int k=1;k<=m;k++) pst[k]=st[k];
			for(int k=1;k<=tot[a[i+1]];k++)
			{
				for(int l=1;l<=m;l++) st[l]=pst[l];
				bool f=true;
				int sum=0;
				for(int l=1;l<=m&&f;l++)
				{
					int u=sta[a[i+1]][k][l];
					if(u>st[l]) f=false;
					if(u>0) sum+=c[i+1][l];
					st[l]-=u;
				}
				if(f)
				{
					int idx=getval();
					tmin(dp[i+1][idx],dp[i][j]+sum);
				}
			}
		}
	}
	int ans=inf;
	for(int i=0;i<=mxval;i++) tmin(ans,dp[n][i]);
	printf("%d\n",ans==inf?-1:ans);
	return 0;
}
复制代码