把状态拆成长链来跑网络流（转化为最小割）：LibreOJ - 2384

2023-12-18 13:02:46

https://vj.imken.moe/contest/598718#problem/C

一个点要确定一个取值，然后每个取值还有代价，我们就拆成一条链：

在这里插入图片描述

源汇点就可以连对应代价的差分

然后题目肯定有某些一堆限制，关于某两条链的取值有什么限制，我们就可以在链之间连很多很多无穷的边来解决，比如：

在这里插入图片描述

这就代表如果第一条链 ≥ 3 \ge 3 ≥3，则第二条链取值 < 5 < 5 <5。

此题同理。

文章来源:https://blog.csdn.net/zhangtingxiqwq/article/details/135058691
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。