CF 808F - Card Game 二分图最大点权独立集网络流最小割

绝地灬酷狼 2022-01-10 11:15 183阅读 0赞

## 题意：给你一些卡片，每个卡片有价值，魔法值，等级。现在要你组成一个卡组，使得卡组里面任意两个数魔法值相加不是质数，并且价值之和大于k。问你需要达到的最低等级，你可以使用等级小于等于你自己等级的卡片。 ##

## 题解：如果我们将加起来为素数的任意两个数连边，那么我们就是要求一个独立集，使得点权之和大于k。而且我们发现，两数相加为质数，一定是一个奇数，一个偶数（除了两个1相加）的二分图。1的问题怎么解决？ 由于只能选择最多一个1，所以我们保留权值最大的那个1，然后再跑二分图最大点权独立集即可。二分一下答案。建立源点和汇点之后，就变成了裸的的最小割问题，最大点权独立集 = 总权值-最小点权覆盖值(最小割)，建图如下。 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW53ZWkwODIy_size_16_color_FFFFFF_t_70][]

## 总结：经典的最小割模型，对于一种情况的最大能量，就是该图的能量总和-最小割。 ##

## 代码：待补。参考[https://blog.csdn.net/c6376315qqso/article/details/82846785][https_blog.csdn.net_c6376315qqso_article_details_82846785]、[https://www.cnblogs.com/antiquality/p/10351543.html][https_www.cnblogs.com_antiquality_p_10351543.html]。 ##

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW53ZWkwODIy_size_16_color_FFFFFF_t_70]: /images/20220110/15812c970a7a489a9ca1d6fee08f6f07.png
[https_blog.csdn.net_c6376315qqso_article_details_82846785]: https://blog.csdn.net/c6376315qqso/article/details/82846785
[https_www.cnblogs.com_antiquality_p_10351543.html]: https://www.cnblogs.com/antiquality/p/10351543.html