Match: Online Dating Service Program For Matching Couples

Question

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.
 
  3
  4
  1 1
  1 2
  2 2
  3 1
  3 3
  3 4
 
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:
 
  3
  1 1
  2 2
  3 4
 
Your program should be implemented in either C or C++. Please try to make your program fast and memory efficient.

Summary

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