【tyvj1431】分配任务

2014年3月26日1,1540

描述 Description

随着tyvj发展越来越大,管理员的任务越来越重,如何合理的分配任务,成为了一个可研究的命题。Tyvj当前一共有M个需要做的任务,和N位管理员。每一个管理员的上线时间并不是固定的,每一个人有d[i]单位的上线时间,每一位管理员一个单位的时间可以完成一个任务,且一个任务只能由一个管理员来完成(如果更多的管理员参与进来,可能会造成混乱)。每一位管理员的能力有所不同,所以能完成的任务集合可能不相同。最终让所有未完成的任务数量最少。

输入格式 InputFormat

输入文件第一有两个正整数,分别是N和M
下面面N行,每一行表示一位管理员的信息,第一个正整数为d[i],第二个正整数为tot,后面有tot个数,表示第i位管理员可以完成的任务集合。

输出格式 OutputFormat

输出文件仅有一个数,所有未完成任务的最少值。

样例输入 SampleInput [复制数据]

样例输出 SampleOutput [复制数据]

数据范围和注释 Hint

数据范围约定:
20%的数据 n<=10 M<=10 且D[i]=1
60%的数据 n<=50 M<=300 且D[i]<=30
100%的数据 n<=3000 M<=10000 且d[i]<=100

题解

源点向所有管理员连d[i]的边

管理员向可解决的任务连1的边

任务向汇点连1的边

ans=m-最大流