吐槽 这题目真的很吸引人 样例不能复制真是可惜 题目的方格染色以及奇怪的节点让我想起了以前看过的一篇博文,讲最小割的。。 于是这道题就最小割。。。 题解 好吧假设我们不知道这道题要最小割 看着题目给的式子我们需要对它做点事情。 max⎧⎩⎨∑i黑bi+∑i白bi−∑i奇怪pi⎫⎭⎬ 我们令 xi=1 表示点i为黑, xi=0 表示点i为白。那么上面的式子可以写成: max{ ∑max{ xi,0}⋅bi+∑max{ 1−xi,0}⋅wi−∑max{ xi−xj,0}⋅pi} 先在这个式子就与线性规划转化为最小割的式…

2016年1月13日 0条评论 0点热度 阅读全文