题解 CF103E 【Buying Sets】

· · 题解

安利 : 九月杂题选做-洛谷博客 九月杂题选做-cnblogs

双倍经验 : LOJ#6045. 「雅礼集训 2017 Day8」价

首先把价值取反，然后问题转换为求最大权值。

考虑一个最小割模型:

S连向集合，容量INF+权值，割掉这条边相当于不选这个集合；

集合连向集合内的数字，容量INF；

数字连向T，容量INF，割掉这条边相当于选这个数字；

不难发现在最小割方案中，割掉集合连向集合内的数字的边是不优的。

因为有完美匹配，所以对于任意左部点集合 S , |N(S)| \geq |S|, 因此至少会割掉n条边。

又因为边权加上了 INF ,所以不会割掉 >n 条边。

因此不选的集合的个数 + 选的数字个数 = n，所以可以得到选的集合个数 = 选的数字的个数。

然后跑一个最小割即可。

O(Dinic(n,n^2))

代码见 : my solution