Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom1年前

05/10
10:24
二分法 最大流

[bzoj 1305] CQOI2009 dance跳舞

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

第一行包含两个整数n和k。以下n行每行包含n个字符,其中第i行第j个字符为'Y'当且仅当男孩i和女孩j相互喜欢。

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

仅一个数,即舞曲数目的最大值。

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

3 0
YYY
YYY
YYY

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

3

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

N<=50 K<=30

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

二分答案+网络流判定

首先我们二分一个答案mid,在判定是否能举办mid次,那么对于每个次我们可以用最大流根据是否满流(流量为n*mid)来判定,对于每个点我们拆成两个点,分别表示这个人要和他喜欢和不喜欢的人一起跳舞,那么添加源点source,汇点sink,设i为男生,j为女生,那么连接<source,i,mid>表示这个人要跳mid次,同理连接<j,sink,mid>,这样我们保证了每个人都是跳了mid次舞,那么对于每一对儿喜欢关系i,j,连接<i,j,1>,对于不喜欢的i,j连接<i',j',1>,那么我们保证了每个人都可以和所有人跳舞,对于i中的每个点连接<i,i',k>代表这个人最多和k个不喜欢的人跳舞,同理对于j中的每个人连接<j',j,k>,因为每次和不喜欢的人跳舞,一定会经过这条边,所以保证了最多不会和超过k的不喜欢的人跳舞,然后求解二分就行了。

c++:

pascal:

 

[bzoj 1305] CQOI2009 dance跳舞