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

Example for register storage class - computer programming, Example for Regi... Example for Register Storage Class - computer programming? main() { register int i; for (i=0; i { ............... ............... } } /* block exit will free the register

What are the debugging methods you employ while came across , What are the ... What are the debugging methods you employ while came across a problem? A: Debugging with tools such as: 1.      DBG, GDB ,Forte, Visual Studio. 2.      Using tusc to trace

Area under curve, progarm in c for area under curve   #include ... progarm in c for area under curve   #include float start_point, /* GLOBAL VARIABLES */ end_point, total_area; int numtraps;

What is the significance of external declaration, Problem 1 What is the... Problem 1 What is the difference between function declaration and function definition? 2 Write a recursive function to find sum of even numbers from 2 to 10. 3 List some

C program for merge two strings , v\:* {behavior:url(#default#VML);} o\:* ... v\:* {behavior:url(#default#VML);} o\:* {behavior:url(#default#VML);} w\:* {behavior:url(#default#VML);} .shape {behavior:url(#default#VML);} Normal 0

Named what can derived class add?, New data members  New member function... New data members  New member functions  New constructors and destructor  New friends

What is the conditional expression operator, The Conditional Expression Ope... The Conditional Expression Operator An alternate method to using a simple if-else construct is the conditional expressions operator, ?:   A conditional expression operato

For loop, minimum of seven number minimum of seven number

Pebble merchant, c++ program c++ program

Overloading binary operators using friend function, Overloading Binary Oper... Overloading Binary Operators Using Friend Function class SI {float i,p,n,r,a; public: SI(){}; SI(int gp,int gn, int gr); void putdata(void); friend SI operato