COMP572 -- Fall 2004
Input:
The input is read from standard input or a file (your documentation should
indicate which). The first line contains an integer n where n is the number of
nodes of both sides of the bipartite graph. The nodes are referred as x0 to xn-1
and y0 to yn-1. Each of the next n lines of the input contains n numbers. The j-th
integer in the i-th line indicates that the weight of the edge from node xi to
node yj. Note that the weights should be assumed to be integers (positive, 0 or
negative)
You can assume:
n is between 1 and 100.
The absolute weight of all edges is less than 109.
The absolute total weight of the max bipartite matching is less than 109.
Output:
i) Print out the total weight of the max bipartite matching in the first
line.
ii) Print out the a0 to an-1, a permutation of 0 to n-1, in next line where ai
specifies that xi is matched to yai.
iii) Print out the associated feasible labellings of y0 to yn-1.
iv) Print out the associated feasible labellings of x0 to xn-1.
Note that this matching may not be unique. You just need to output one optimal
matching
Follow the format as sample output. Don’t print any other text character. Always
use a space to separate two values.
Sample input: (Hungarian Algorithm, page 15)
3 1 6 0 0 8 6 4 0 1
16 1 2 0 0 2 0 4 6 4
B: (2 person) Implement part (A) and a GUI for the Hungarian Algorithm:
Your program should also include a GUI that includes
Note that, even with the GUI, your program should also permit inputting text data via standard input or from a file following the specifications from part (A)
This page was released on November 19, 2004 and last revised on 11/19/2004 13:39 +0800