In this question, you will develop a program named “match” to be used by a dating service to form couples. Given the number of gentlemen, the number of ladies, and a list of acceptable pairings, your program should use a network flow based approach to form as many couples as possible. Let m be the # of gentlemen and n be the # of ladies. In this question, each gentleman is represented by an index between 1 and m, and each lady is represented by an index between 1 and n. The inputs are specified in a text file in the format below:
<# of gentlemen>
<# of ladies>
<gentleman in 1st acceptable pairing> <lady in 1st acceptable pairing>
<gentleman in 2nd acceptable pairing> <lady in 2nd acceptable pairing>
<gentleman in last acceptable pairing> <lady in last acceptable pairing>
The output file of your program should include the number of couples formed and a list of those couples. For example, the following input file represents a case with 3 gentlemen, 4 ladies and 6 potential pairings.
The best matching solution consists of 3 pairs and one feasible solution is that gentleman 1 is matched to lady 1, gentleman 2 is matched to lady 2, and gentleman 3 is matched to lady 4. (Note that there are many other feasible solutions with 3 pairs.) The corresponding output file of your program is shown below:
Your program should be implemented in either C or C++. Please try to make your program fast and memory efficient.
The question belongs to Computer Science and it is about writing a program either in C or C++ for an online dating service, where one needs to pair men and women based on a network flow approach.
Total Word Count NA