Suppose we have a set of N agents and a set of N tasks.Each agent can only perform exactly one task and there is a cost associated with each assignment. We would like to find out an assignment which results in the least total cost. Your task is to write a c++ program to implement the branch and bound algorithm to solve this assignment problem.
Your program should read input data from a input file named "infile.txt". The format for the input file is as follows: First line is an integer N representing the number of agents and the number of jobs. In the next N lines, each line j (1 ≤ j ≤ N) consists of N integers representing the cost of assigning agent j to each of the N tasks.
Figure 1 gives you an example of the input format. For example, the cost of assigning agent 1 to task 1, 2, 3 and 4 are 11, 12, 18 and 40 respectively.
|
4
11 12 18 40
14 15 13 22
11 17 19 23
17 14 20 28
|
Figure 1
|
Total cost: 61
(1,1)
(2,3)
(3,4)
(4,2)
|
Figure 2
Output, to standard output, will consist of:
- Total cost of the assignment
- In the next N lines, each line j (1 ≤ j ≤ N) shows the task assignment for agent j in the format "(j,k)", which means agent j is assigned to task k.
Figure 2 gives you an example of the output screen for the input file in Figure 1.