Codeforces 1519F - Chests and Keys（暴搜+以网络流为状态的 dp）
Codeforces 1519F - Chests and Keys（暴搜+以网络流为状态的 dp）
难度终于出来了……又独立切掉一道 *3200，凯信（所以我已经独立切掉三道 *3200 了？）
首先考虑我们已经知道了每个宝箱上有哪些锁，怎样求 Bob 的最大利益，这显然就是一个最大权闭合子图的模板，我们将箱子看作左部点，钥匙看作右部点，对于每个箱子 i 我们连一条 S 到该箱子表示的点，容量为 ai 的边，对于每个钥匙 j 我们连一条该钥匙所表示的点到 T，容量为 bi 的边，最后对于每个箱子 i 上挂有的锁 j 连一条箱子 i 表示的点到钥匙 j 表示的点，容量为 ∞ 的边，根据最小割那套理论最大利益就是 ∑ai 减去建出图来的最小割即最大流即可。我们希望最大利益 ≤0，故最大流需 ≥∑ai，而显然与源点相连的点的边的总流量都只有 ∑ai，故所有与源点相连的边必须满流。
因此题目转化为，最少需要花费多少的代价在左部点与右部点间连边，使得得到的图跑完最大流后所有与源点相连的边都满流，直接用贪心之类的方法显然是不可行的，不过注意到此题数据范围出乎意料地小——ai≤4,n≤6，也就是说所有与源点相连的边的流量总共最多只有 (4+1)6=15625 种可能，我们考虑以此为状态设计 dp，我们记 dpi,j 表示已经连好了前 i 个右部点相关的边，当前所有与源点相连的边的流量的状态为 j 的最小花费（注：在下文中，为了表述方便，我们用一个 n 元组 (x1,x2,⋯,xn) 表示这样的状态 j，xi 表示源点与 i 相连的边的流量），考虑转移，我们考虑 i+1 到汇点的 bi+1 的流量的来源，假设 j→i+1 的边流了 yj 的流量，那么需要的代价 C=∑j=1n[yj>0]×cj,i+1，总转移方程为 dpi+1,(x1+y1,x2+y2,⋯,xn+yn)←dpi,(x1,x2,⋯,xn)+C，至于这个 yj 怎么处理，再套个背包类的 dp 当然是没问题的，不过由于 bi 数据范围也很小，因此可以直接无脑暴搜 yi，显然 yi 的个数是与划分数有关的，根据隔板原理暴搜次数最多是 (94)+(83)+(72)+(61)+(50)=210，是不会出问题的。最后输出 dpn,(a1,a2,⋯,an) 即可
最后是这个状态怎么处理，我的做法是将 (x1,x2,⋯,xn) 进行八进制压缩压成一个 218 以内的数再重新编号，如果用 vector 保存复杂度会多一个 n，不知道能不能跑得过（大雾
总复杂度 15625×62×210，不过似乎跑得飞快？最慢的一个点才跑了 31ms。
Copyconst 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;
}作者： ET2006
出处：https://www.cnblogs.com/ET2006/p/Codeforces-1519F.html