错误集锦

发布于 2018-03-03  422 次阅读


BZOJ 2132 - 圈地计划

经典模型,棋盘黑白染色,有不同贡献;如果相邻的两个格子一样或者不一样颜色就加一个贡献。显然有一个拆点之后相邻格子代表点连边的做法。只有一个问题:如图这样赋值的话,中间的点既不是黑色,也不是白色。
网上有人提及了一个做法,就是不拆点直接连双向边。可以,但是会时间超限,真的会(bzoj数据强强)
真正的解决方法是把左边和右边的边加上一个大权值,使得最小割不会同时割左右边,在最后由于一定会割掉n个左右的边,总答案减去节点数乘大权值即可。


血まみれからの方がさ,勝つ時にはカッコイイだろう.