TouchStone
  Please Login
ログイン 登録
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P1512
  • 問題
  • P1512奶牛食品
    制限 : 時間制限 : 10000 MS   メモリ制限 : 65536 KB
    問題説明

    FJ的奶牛们只吃各自喜欢的一些特定的食物和饮料,除此之外的其他食物和饮料一概不吃。某天FJ为奶牛们精心准备了一顿美妙的饭食,但在之前忘记检查奶牛们的菜单,这样显然是不能不能满足所有奶牛的要求。但是FJ又不愿意为此重新来做,所以他他还是想让尽可能多的牛吃到他们喜欢的食品和饮料。

    FJ提供了F (编号为1、2、…、F)种食品并准备了D (编号为1、2、…、D)种饮料,他的N头牛(编号为1、2、…、N)都已决定了是否愿意吃某种食物和喝某种饮料。FJ想给每一头牛一种食品和一种饮料,使得尽可能多的牛得到喜欢的食物和饮料。

    每一种食物和饮料只能由一头牛来用。例如如果食物2被一头牛吃掉了,没有别的牛能吃到食物2。

    入力形式

    第一行包含三个用空格分开的整数N,F和D;

    接下来的N行描述每个奶牛的信息:
    第i+1行的前两个整数为F_i和D_i,接下来的F_i个整数表示奶牛i喜欢的食品编号,再接下来的D_i个整数表示奶牛i喜欢的饮料编号。

    出力形式

    仅一行一个整数,表示FJ最多能让多少头奶牛吃到自己喜欢的食品和饮料。

    サンプル入力 1

    4 3 3
    2 2 1 2 3 1
    2 2 2 3 1 2
    2 2 1 3 1 2
    2 1 1 3 3 

    サンプル出力 1

    3

    サンプル入力 2

    10 10 12
    1 1 7 4
    1 1 8 4
    3 2 3 4 9 5 9
    2 0 3 10
    0 2 4 12
    1 0 9
    2 2 5 8 6 8
    0 2 7 10
    0 2 8 12
    3 2 1 2 9 2 9

    サンプル出力 2

    4

    ヒント

    输入数据表明:奶牛1喜欢的食物1、2;喜欢喝饮料3、1;奶牛2喜欢的食物2、3;喜欢喝饮料1、2;奶牛3喜欢的食物1、3;喜欢喝饮料1、2;奶牛4喜欢的食物1、3;喜欢喝饮料3;

    那么下面的分配方法将是最优的:奶牛1不给食品和饮料;奶牛2分配食物2和饮料2;奶牛3分配食物1和饮料2;奶牛4分配食物3和饮料4。

    1<=F<=100,1<=D<=100,1<=N<=100


    ソース  网络流 usaco open 2007 gold dining