320SC语言程序辅导、辅导c/c++，Java编程

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.

1

Sample Input

2

3 7

PrincessCindy

MrBig

BillGates

Zena MrBig

BuckJock PrincessCindy BillGates

DrMJD MrBig PrincessCindy BillGates

MissyC MrBig BillGates

MicheleJackson MrBig

MrsSmith

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

20 20 non-accepting