In this assignment, 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 m be the # of ladies. In this assignment, each gentleman is represented by an index between 1 and m, and each lady is represented by an index between 1 and m. The inputs are specified in a text file in the format below:

<# of gentlemen>

<# of ladies>

...

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 your best to make your program fast and memory efficient. Several input files are posted. For submission, please email to the TA your source code and the output file for each input file. For each input file, please also report the runtime, and the processor model and clock frequency of the machine that you used.

Posted Date: 2/19/2013 6:38:52 AM | Location : United States

Ask an Expert

Related Discussions:- Program to develope dating service to form couples, Assignment Help, Ask Question on Program to develope dating service to form couples, Get Answer, Expert's Help, Program to develope dating service to form couples Discussions

Write discussion on Program to develope dating service to form couples
Your posts are moderated

Write your message here..

Related Questions

Sp, Write a program to find the area under the curve y = f(x) between x = a... Write a program to find the area under the curve y = f(x) between x = a and x = b, integrate y = f(x) between the limits of a and b. The area under a curve between two points can b

Explain briefly about class and objects, Question 1. Explain Briefly ab... Question 1. Explain Briefly about class and objects. 2. Create a class string which stores a string value. Overload ++ operator which converts the characters of the string t

What is the process of access the static member of a class?, Normal 0 ... Normal 0 false false false EN-US X-NONE X-NONE

Luminous Jewels - The Polishing Game, plaese tell the full program for the ... plaese tell the full program for the above given topic with the input and output

How to insert values in array - c++ program, How to insert values in array ... How to insert values in array - c++ program: Write a program to insert values in array void main() { int a[2][3][2]={                                 {

Why should i employ new instead of truthful old malloc()?, Why should I emp... Why should I employ new instead of truthful old malloc()? A: Constructors/destructors, type safety, overridability. Constructors/destructors: unlike malloc(sizeof(Fred)), new

Luminous Jewels - The Polishing Game, Damjibhai and Shamjibhai are two jewe... Damjibhai and Shamjibhai are two jeweler friends. They decide to play a simple game. The game comprises of removing the jewels for polishing, turn by turn. Once a jewel is removed

Stack, c++ program to to implement multiple stacks using single array c++ program to to implement multiple stacks using single array

Functions, differentiate between inbuilt and user defined functions differentiate between inbuilt and user defined functions

Assign random integers to the variable, (Random Numbers) Write statements t... (Random Numbers) Write statements that assign random integers to the variable n in the following ranges: a) 1 ≤ n ≤2 b) 1 ≤ n ≤100 c) 0 ≤ n ≤9 d) 1000 ≤ n ≤1112 e)