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

Download Full Solution

Comments

  • HWA
    Rasha

    this is a very good website

  • HWA
    maani

    I have 50 questions for the same test your page is showing only 28

  • HWA
    joeanne

    hi can you please help or guide me to answer my assignments. thanks

  • HWA
    joeanne

    hi can anyone help or guide me to my assignments. thanks

  • HWA
    Monik


  • HWA
    Cristina

    This solution is perfect ...thanks

  • HWA
    Janete

    Hello Allison,I love the 2nd image that you did! I also, had never heard of SumoPaint, is something that I will have to exolpre a bit! I understand completely the 52 (or so) youtube videos that you probably watched. Sometimes they have what you want, sometimes they don't! However, it is always satisfying when you are able to produce something that you have taught yourself. Great job!Debra 0 likes

  • HWA
    Sandeep

    Perfect bank of solution. 

  • HWA
    Oxana

    great !

  • HWA
    Paul Brandon-Fritzius

    thanks for the quick response. the solution looks good. :)

  • HWA
    tina Johnson

    thnx for the answer. it was perfect. just the way i wanted it. 

  • HWA
    Giuseppe

    works fine.