[BZOJ1305/Luogu3153][CQOI2009]dance跳舞(网络流)

发布于 2018-02-26  159 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1305/Luogu3153][CQOI2009]dance跳舞(网络流)

8### Description
一次舞会有n个男孩和n个女孩。每首曲子开始时,所有男孩和女孩恰好配成n对跳交谊舞。每个男孩都不会和同一个女孩跳两首(或更多)舞曲。有一些男孩女孩相互喜欢,而其他相互不喜欢(不会“单向喜欢”)。每个男孩最多只愿意和k个不喜欢的女孩跳舞,而每个女孩也最多只愿意和k个不喜欢的男孩跳舞。给出每对男孩女孩是否相互喜欢的信息,舞会最多能有几首舞曲?

Http

BZOJ
Luogu

Tag

网络流

解决思路

对于每一个人拆成两个点,一个点表示喜欢的,另一个点表示不喜欢的,若两个人互相喜欢,那么就连接两个表示的点,否则连接两个表示不喜欢的点。然后,由于要求一个人最多只与\(k\)个不喜欢的人跳,那么一个人拆成的两个点之间的容量就为\(k\)。那么接下来就是枚举轮数,每一次修改对应的从源点连出的边和到汇点的边。若当前最大流等于人数乘以轮数,则可以继续,否则轮数--

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1305/Luogu3153][CQOI2009]dance跳舞(网络流)


HNCJ OIer