TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P1516
  • 問題
  • P1516跳舞
    制限 : 時間制限 : 10000 MS   メモリ制限 : 65536 KB
    問題説明

    一次舞会有n个男孩和n个女孩。每首曲子开始时,所有男孩和女孩恰好配成n对跳交谊舞。每个男孩都不会和同一个女孩跳两首(或更多)舞曲。

    有一些男孩女孩相互喜欢,而其他相互不喜欢(不会“单向喜欢”)。每个男孩最多只愿意和k个不喜欢的女孩跳舞,而每个女孩也最多只愿意和k个不喜欢的男孩跳舞。

    给出每对男孩女孩是否相互喜欢的信息,舞会最多能有几首舞曲?

    入力形式

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

    出力形式

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

    サンプル入力

    Input 1:
    3 0
    YYY
    YYY
    YYY

    Input 2:
    3 0
    YYY
    YYN
    YNY

    Input 3:
    2 0
    YN
    YN

    Input 4:
    2 1
    YN
    YN

    サンプル出力

    Output 1:
    3

    Output 2:
    2

    Output 3:
    0

    Output 4:
    1

    ヒント

    N<=50
    K<=30


    ソース  CQOI2009 T3 网络流