关于程序员:320SC

Computer Science 320SC – (2021)
Programming Assignment 6
Due: Sunday, October 24th
Requirements
This last assignment lets you get familiar with network flow 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
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.
Output
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
[case (b)].
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.

【腾讯云】轻量 2核2G4M,首年65元

阿里云限时活动-云数据库 RDS MySQL  1核2G配置 1.88/月 速抢

本文由乐趣区整理发布,转载请注明出处,谢谢。

您可能还喜欢...

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据