This last assignment lets you get familiar with network ow algorithmic design and development. It is
worth 5% of your total course marks. Please try and test with your own generated input cases before
submitting to the automated marker.
Task: Dating a Celebrity
Actors and actresses, sport stars, and some famous geeks have donated their time to support the \Dating
a Celebrity” global charity event. Each star promised to date as many fans to support the charity. Each
fan will date one, and only one, celebrity from her/his nominated set of favorite preferences. You also
want to support this event using your algorithmics skills to help match fans to celebrties. Your task is
to write a program that reads a listing of the names of the celebrities voluntering their time, a listing of
the donor fans along with their favorite celebrites. You should assign the celebrities to one or more fans,
for a date, in a way that minimizes the maximum number of dates that any celebrity has to attend.
Input begins with an integer E on a line by itself, 1 E 2000, that represents the number of scenarios
where each scenario describes a charity event. Each event description begins with two integers N and
M, separated by a single space, on a line by themselves. The integer N represents the number of
celebrities and M represents the number of donor fans. Each of the next N lines contains the name of
a celebrity. Each of the following M lines, one line per donor, starts with the name of a donor followed
by the names of her/his favourite stars, if any. Names are separated by a single space, and the name
of a celebrity cannot appear more than once in each line. Each name (celebrity or fan) consists of a
single word; that is, a string with no white spaces. The names of celebrities and fans are all distinct
from each other. 1 <= N <= 50 and 1 <= M <= 2000.
We have two required programs. The first program will give you one marks for being able to parse the
input and decide a lower bound on the number of dates needed [case (a)]. The second program will
give you four marks (two each for easy and hard input test cases) for obtaining the optimal answer
For each charity event, print the event number (starting with 1, and using the format in the samples)
followed by a single space and then an integer (round up if needed) describing (a) the `number of fans
who want to play with a star’ divided by N=`number of celebrities’ and (b) the maximum number of
rounds any star has to play.
本网站支持 Alipay WeChatPay PayPal等支付方式
E-mail: firstname.lastname@example.org 微信号:vipnxx