题目描述

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

输入

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

输出

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

样例输入

3 0

YYY

YYY

YYY

样例输出

3


调了半天发现二分写错了

对于女生和男生都拆成两个点处理i和i’

规定

i为男生,j为女生,+2n为不喜欢

so..

1-n 男生喜欢

n+1-2n 女生喜欢

2n+1-3n 男生不喜欢

3n+1-4n 女生不喜欢


对于

  • i like j i->j 1 这保证了只跳一曲
  • i dislike j i+2n->j+2n 1
  • s->i mid
  • j->t mid
  • i i->i+n k 这保证了不超过K曲
  • j j+n->j k

那么,若网络满流

就是ans>=mid*n

说明这些曲子可以进行完

枚举或二分都行

 

分类: 图论题解

说点什么

avatar
  Subscribe  
提醒