|
320SC编程辅导、辅导Java，c/c++程序
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
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.
1
Sample Input
2
3 7
PrincessCindy
MrBig
BillGates
AdamSandman PrincessCindy
3 6
CaptainKirk
MrSpock
Xindi
FakeZena MrSpock
BuckGuy MrSpock
DrLove MrSpock
MissyC MrSpock
BootyJackson MrSpock
AliceSandy CaptainKirk Xindi
Sample Output for case (a): lower bound
Event 1: 2
Event 2: 2
Sample Output for case (b): optimal answer
Event 1: 2
Event 2: 5
请加QQ：99515681 或邮箱：99515681@qq.com WX：codehelp
|
