Codeforces 1519F - Chests and Keys（暴搜+以网络流为状态的 dp）

难度终于出来了……又独立切掉一道 *3200，凯信（所以我已经独立切掉三道 *3200 了？）

首先考虑我们已经知道了每个宝箱上有哪些锁，怎样求 Bob 的最大利益，这显然就是一个最大权闭合子图的模板，我们将箱子看作左部点，钥匙看作右部点，对于每个箱子 \(i\) 我们连一条 \(S\) 到该箱子表示的点，容量为 \(a_i\) 的边，对于每个钥匙 \(j\) 我们连一条该钥匙所表示的点到 \(T\)，容量为 \(b_i\) 的边，最后对于每个箱子 \(i\) 上挂有的锁 \(j\) 连一条箱子 \(i\) 表示的点到钥匙 \(j\) 表示的点，容量为 \(\infty\) 的边，根据最小割那套理论最大利益就是 \(\sum a_i\) 减去建出图来的最小割即最大流即可。我们希望最大利益 \(\le 0\)，故最大流需 \(\ge\sum a_i\)，而显然与源点相连的点的边的总流量都只有 \(\sum a_i\)，故所有与源点相连的边必须满流。

因此题目转化为，最少需要花费多少的代价在左部点与右部点间连边，使得得到的图跑完最大流后所有与源点相连的边都满流，直接用贪心之类的方法显然是不可行的，不过注意到此题数据范围出乎意料地小——\(a_i\le 4,n\le 6\)，也就是说所有与源点相连的边的流量总共最多只有 \((4+1)^6=15625\) 种可能，我们考虑以此为状态设计 \(dp\)，我们记 \(dp_{i,j}\) 表示已经连好了前 \(i\) 个右部点相关的边，当前所有与源点相连的边的流量的状态为 \(j\) 的最小花费（注：在下文中，为了表述方便，我们用一个 \(n\) 元组 \((x_1,x_2,\cdots,x_n)\) 表示这样的状态 \(j\)，\(x_i\) 表示源点与 \(i\) 相连的边的流量），考虑转移，我们考虑 \(i+1\) 到汇点的 \(b_{i+1}\) 的流量的来源，假设 \(j\to i+1\) 的边流了 \(y_j\) 的流量，那么需要的代价 \(C=\sum\limits_{j=1}^n[y_j>0]\times c_{j,i+1}\)，总转移方程为 \(dp_{i+1,(x_1+y_1,x_2+y_2,\cdots,x_n+y_n)}\leftarrow dp_{i,(x_1,x_2,\cdots,x_n)}+C\)，至于这个 \(y_j\) 怎么处理，再套个背包类的 \(dp\) 当然是没问题的，不过由于 \(b_i\) 数据范围也很小，因此可以直接无脑暴搜 \(y_i\)，显然 \(y_i\) 的个数是与划分数有关的，根据隔板原理暴搜次数最多是 \(\dbinom{9}{4}+\dbinom{8}{3}+\dbinom{7}{2}+\dbinom{6}{1}+\dbinom{5}{0}=210\)，是不会出问题的。最后输出 \(dp_{n,(a_1,a_2,\cdots,a_n)}\) 即可

最后是这个状态怎么处理，我的做法是将 \((x_1,x_2,\cdots,x_n)\) 进行八进制压缩压成一个 \(2^{18}\) 以内的数再重新编号，如果用 vector 保存复杂度会多一个 \(n\)，不知道能不能跑得过（大雾

总复杂度 \(15625\times 6^2\times 210\)，不过似乎跑得飞快？最慢的一个点才跑了 31ms。

const int MAXN=6;

const int MAXP=15625;

int n,m,a[MAXN+3],b[MAXN+3],c[MAXN+3][MAXN+3];

ll dp[MAXN+3][MAXP+5];

int rid[MAXP+5],id[1<<18];

int idnum=0;

void dfs(int x,int cur){

	if(x==n+1){rid[++idnum]=cur;id[cur]=idnum;return;}

	for(int i=0;i<=a[x];i++) dfs(x+1,cur+(i<<(3*(x-1))));

}

void dfs2(int x,int t,int msk,int lft,ll val){

	if(!lft||x==n+1){chkmin(dp[t][id[msk]],val);return;}

	for(int i=0;i<=min(a[x]-(msk>>(3*(x-1))&7),lft);i++){

		dfs2(x+1,t,msk+(i<<(3*(x-1))),lft-i,val+(i>0)*c[x][t]);

	}

}

int main(){

	scanf("%d%d",&n,&m);int sa=0,sb=0;

	for(int i=1;i<=n;i++) scanf("%d",&a[i]),sa+=a[i];

	for(int i=1;i<=m;i++) scanf("%d",&b[i]),sb+=b[i];

	if(sa>sb) return puts("-1"),0;

	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&c[i][j]);

	dfs(1,0);memset(dp,63,sizeof(dp));dp[0][id[0]]=0;

	for(int i=0;i<m;i++){

		vector<int> pos;

		for(int l=1;l<=idnum;l++){

			if(dp[i][l]>=0x3f3f3f3f3f3f3f3fll) continue;

			dfs2(1,i+1,rid[l],b[i+1],dp[i][l]);

		}

	} int lst=0;for(int i=1;i<=n;i++) lst|=(a[i]<<(3*(i-1)));

	if(dp[m][id[lst]]<0x3f3f3f3f3f3f3f3fll) printf("%lld\n",dp[m][id[lst]]);

	else puts("-1");

	return 0;

}

巴特西

Codeforces 1519F - Chests and Keys（暴搜+以网络流为状态的 dp）

最新文章

热门文章