P3153 [CQOI2009]跳舞

    • 183通过
    • 614提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 最大流 网络流 贪心 2009 重庆
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

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

    输入输出格式

    输入格式:

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

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    3 0
    YYY
    YYY
    YYY
    输出样例#1: 复制
    3

    说明

    N<=50 K<=30

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。