BZOJ1305 - Click Here
Description
一次舞会有n个男孩和n个女孩。每首曲子开始时，所有男孩和女孩恰好配成n对跳交谊舞。每个男孩都不会和同一个女孩跳两首（或更多）舞曲。有一些男孩女孩相互喜欢，而其他相互不喜欢（不会“单向喜欢”）。每个男孩最多只愿意和k个不喜欢的女孩跳舞，而每个女孩也最多只愿意和k个不喜欢的男孩跳舞。给出每对男孩女孩是否相互喜欢的信息，舞会最多能有几首舞曲？
Input
第一行包含两个整数n和k。以下n行每行包含n个字符，其中第i行第j个字符为’Y’当且仅当男孩i和女孩j相互喜欢。
N<=50,K<=30
Output
仅一个数，即舞曲数目的最大值。
Solutions
不难发现，对于任意男孩与任意女孩，关系都是唯一的。换句话说，喜欢与不喜欢关系是分别独立的。
因此，可以很容易得到一个网络流的建图：
对于每个男孩或女孩$i$，都拆分成$i,i’$。
对于每个喜欢关系$(i,j)$，连边$(i,j,1)$；对于每个不喜欢关系$(i,j)$，连边$(i’,j’,1)$。
对于至多k个不喜欢的限制，只需要连边$(i,i’,k),(j,j’,k)$；其中$i$为男孩，$j$为女孩。
这样，对于该图的最大流，即为最多能够匹配的数量。
但是题目求的是最多舞曲数，也就是说能够完整匹配多少次。
很显然，如果直接对最多匹配数进行处理，是无法得到最优解的。因为跑最大流时，对于相同流量的情况，是无法处理的。
注意到答案具有单调性，因此可以二分答案来求最多舞曲数。
建立超级源点和超级汇点。对于每个男孩$i$，连边$(S,i,p)$；对于每个女孩$j$，连边$(j,T,p)$。其中p为二分的答案。若满流，则答案p合法。
CODE
CODE - Click Here