TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1979
  • 题目
  • P1979【二分图】投票
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    小 k 同学正在玩一个游戏,在游戏中他扮演了一个马戏团的老板,现在小 k同学需要利用马戏团中的A只猫和B只狗举办一次表演,表演之前他让观众进行了投票,投票的类容是:
    我想看到第___号猫/狗的表演,不想看到第___号猫/狗的表演。注意到每个观众都是更喜欢猫或更喜欢狗,所以两个空后面一定会被勾上不同的内容。喜欢猫的观众会在第一空后面选择猫,第二空后面选择狗;反之就会在第一空后面选择狗,第二空后面选择猫。对于每一个观众,只有当 TA投票的内容都被满足了(即 TA想看到的动物出场表演,TA不想看到的动物不参与表演)的时候,TA才会来看表演。当然啦,看表演是要付门票钱的,作为马戏团的老板,小 k自然是希望来的人越多越好了。他想找到一个安排动物表演的方案,使得来看表演的观众尽量多。

    输入格式

    第1行 3 个正整数n、m、k,分别表示猫、狗和观众的数量
    第2~k + 1行,每行描述了一个观众的投票内容。
    首先输入一个字符 C或 D紧接着是一个数字,表示某个观众想看到的动物,然后是一个空格隔开,接下去又是一个 C或 D 加上一个数字,表示这个观众不想看到的动物,同一行中一定不会出现两个 C或两个 D。

    输出格式

    输出一行一个正整数,表示小 k在最优的安排下可以吸引多少观众来看表演。

    样例输入 1

    1 2 4
    C1 D1
    C1 D1
    C1 D2
    D2 C1

    样例输出 1

    3

    样例输入 2

    3 8 13
    D5 C1
    D5 C3
    D2 C3
    D8 C3
    D5 C1
    C2 D4
    C2 D2
    D1 C1
    D3 C1
    C2 D7
    D6 C3
    C2 D2
    D5 C1

    样例输出 2

    12

    提示

    对于 25%的数据,n,m ≤ 10, k ≤ 25 ;
    对于 100%的数据,n,m ≤ 300, k ≤ 500.