hdu 5076 Memory

题目链接

这道题也是蛮有趣的。

有$2^n$个内存位，每个位置可以放一个数字，范围为$[0,2^m)$，第$i$个位置放$j$可以得到$w(i,j)$的收益，每个位置还有一个临界值$t_i$以及一个$u_i$。

除此之外，一旦有两个位置$a,b$满足以下两个条件，可额外获得$u_a$ xor $u_b$的收益。

• $a$和$b$在二进制下只有一个bit不同。
• $a$位置放的数不小于$t_a$或者$b$位置放的数不小于$t_b$。

求最大收益的一组方案。

如果不考虑额外收益，显然每个位置$i$放的都是使得$w(i,j)$最大的$j$。而考虑额外收益后，需要分两种情况，放的数小于等于$t_i$以及大于$t_i$。每种情况保留下来的一样都是使得$w(i,j)$最大的$j$。

由题意知，对于每一组满足条件一的$a,b$，只有两个位置都小于$t_a,t_b$时才获得不到收益。从这里就能大概看出一个最小割模型了，割就是要抛弃的收益。

对于比较常见的模型一般都是一个二分图，而这题看起来“选择同侧”的点有额外代价的条件似乎很迷惑人，但注意到第一个条件，就可以发现可以利用二进制1的个数的奇偶性来让模型变成”选择异侧”的点有额外代价。

最后的建模过程就很好理解了。

• 对于每个位置拆成两个点，左边源右边汇。
• 如果这个位置的index有奇数个1，左边连小于的$w$，右边连大于等于的$w$。
• 如果这个位置的index有偶数个1，左边连大于等于的$w$，右边连小于的$w$。
• 每个位置左边往右边连一条inf的弧，代表这两个点不能都不割。
• 对于每组$a,b$，从奇数的小于连向偶数的小于，$u_a$ xor $u_b$。
• 为了避免负流量可以把所有w加一个1024，不影响最后结果。
• 总之建出来是个二分图。
• 最后建完就可以发现其实可以不用拆点，但拆了还是更好理解一些。

最后所有的收益加起来减掉最小割就是最大收益。

Written with StackEdit.