GYM 101128 F.Landscaping【最小割--还不懂】
2021-04-14 02:26
阅读：496
思路：
很显然我们不能直接Dp，因为我们当前的块如果变化了，会对之前很多结果进行了影响，我们考虑多加维度取消这个后效性无果，不妨考虑网络流。
我们要求最小花费，不难想到最小割，那么考虑建图。
①首先我们可以将点分成两类，这样我们使得低地分成一类，剩下的分成一类，那么就构成了二分图。
我们将源点连入各个低地点，流为B，我们再将各个高地点连入汇点，流也为B.
②然后我们将各个相邻的点，都要连上，流为A.
这样我们只有当高地和低地同时存在的时候，才会有所花费（有流从源点到汇点。）。
建好图之后跑最大流即可。
文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：GYM 101128 F.Landscaping【最小割--还不懂】
文章链接：http://soscw.com/index.php/essay/75463.html
文章标题：GYM 101128 F.Landscaping【最小割--还不懂】
文章链接：http://soscw.com/index.php/essay/75463.html
评论
亲，登录后才可以留言！