快乐的一天从AC开始 | 20210724 | P1231

题目链接

(补20210718)

心路历程

看完题目,这不网络流嘛?

看完数据范围,这是网络流嘛?

陷入沉思

思路

其实就是Dinic求最大流。一般情况下Dicic的时间复杂度为(O(n^2m)),但是这题所有边的流量至多为(1),且满足每个节点至多只有一条入边或者至多只有一条出边,在这样的图上Dinic的时间复杂度为(O(msqrt{n})),一个很经典的就是二分图。具体分析可以看OI Wiki。

超级源点连向所有练习,练习连向书,书连向所有答案,所有答案连向超级汇点,然后答案就是超级源点到超级汇点的最大流。

然后因为一本书至多只能用一次,所以书要拆点。

然后跑个最大流就完事了。

原文地址:https://www.cnblogs.com/zengzk/p/15055438.html