In the likely event that your team will rank among the first at MIUP 2012, very soon you will be contacted by the big international software companies, all eager to draw on your programming talent. Some will offer a bigger salary, others a fantastic working environment, a challenging project, the opportunity to work with a new technology, or the prospect of a brilliant international career. You will be at a loss, not knowing which offer to accept, fearing to take the wrong decision.

Fear no more! Being a programming person, just write a program to decide for you. May we suggest the Analytical Hierarchy Process, AHP for short? We’ll explain it with an example, which actually can apply to you.

Suppose that after some soul-searching, you have found that you pursue
four objectives for your first job as a software developer: a large
salary (obj_{1}), a challenging project (obj_{2}), a high quality
of living in the city to where you will be relocated (obj_{3}), and
a lot of traveling (obj_{4}).

Not all these objectives are worth the same, for you. For example, in your opinion, a high salary is twice as important as a challenging project and four times as important as a lot of traveling.

You can write down a matrix a, where a_{ij} means that for you,
objective i is a_{ij} times more important than objective j. In
this matrix, a_{ii} = 1 and a_{ij} × a_{ji} = 1, of course.

Objective | 1 | 2 | 3 | 4 | |

1 | 1 | 2 | 3 | 4 | |

2 | 1/2 | 1 | 5 | 7 | |

3 | 1/3 | 1/5 | 1 | 3 | |

4 | 1/4 | 1/7 | 1/3 | 1 |

Next, you normalize the matrix, by dividing each value by the sum of
its column. Then you compute the weight of each objective as the sum
of each line divided by the number of columns. Easy?

Objective | 1 | 2 | 3 | 4 | weight |

1 | 0.4800 | 0.5983 | 0.3214 | 0.2667 | 0.4166 |

2 | 0.2400 | 0.2991 | 0.5357 | 0.4667 | 0.3854 |

3 | 0.1600 | 0.0598 | 0.1071 | 0.2000 | 0.1317 |

4 | 0.1200 | 0.0427 | 0.0357 | 0.0667 | 0.0663 |

Sum | 1.0000 | 1.0000 | 1.0000 | 1.0000 | 1.0000 |

Now suppose you got offers from IBM (job_{1}), in Zurich, from
Microsoft (job_{2}), in London, and from Google (job_{3}) in
Mountain View. In your perspective, job_{1} is twice as important in
terms of salary as job_{3} and four times as important as job_{2},
and job_{3} is six times as important in terms of salary as
job_{2}:

Salary(obj_{1}) | job_{1} | job_{2} | job_{3} | |

job_{1} | 1 | 4 | 2 | |

job_{2} | 1/4 | 1 | 1/6 | |

job_{3} | 1/2 | 6 | 1 |

Repeating the same steps for the other 3 objectives, normalizing the 4
matrices and calculating the weights, we get the preferences of the
jobs in respect to the objectives:

obj_{1} | obj_{2} | obj_{3} | obj_{4} | ||

job_{1} | 0.5222 | 0.2364 | 0.1524 | 0.2014 | |

job_{2} | 0.0955 | 0.0623 | 0.7208 | 0.6806 | |

job_{3} | 0.3823 | 0.7013 | 0.1268 | 0.1179 |

The estimation of the preferences of each job in respect to each objective (the weight) is given by the average of the a_{i,j}, j=1,..,3 of the normalized matrix.

Finally, to compute the combined scores of each job, you must add the
product of the objective weight and preference. For example, the score
of job_{1} is given by:

score(job_{1}) = 0.5222 × 0.4166 + 0.2364 × 0.3854 + 0.1524 × 0.1317 + 0.2014 × 0.0663.

Your task is to write a program that given the objectives and their relative worth and the job offers, and you appreciation of their relative value for each objective, ranks the job offers using the AHP method.

The first line contains two integers, N and M, separated by a single space, indicating respectively the number of objectives and number of jobs.

The second line contains a positive integer P that indicates how many pairwise objectives comparison will follow, followed by P lines with 3 integers in the form “A B I”, indicating that objective A is more important I times than objective B. The value of the missing pair comparisons is 1. The pairs can come in any order and the same pair of objectives cannot appear multiple times.

Then come exactly N groups of pairwise jobs comparisons, one for each of the objectives. The i-th group corresponds to objective i. The input format is the same as the pairwise objectives comparison.

The output file consists of a single line (including the newline character) displaying the number of the M jobs ordered by descending score, and separated by single spaces. You can be assured that there will never be ties in the combined scores of two different jobs.

2 ≤ N,M ≤ 50 | number of objectives and number of jobs |

2 ≤ I ≤ 9 | intensity of importance |

4 3 6 1 2 2 1 3 3 1 4 4 2 3 5 2 4 7 3 4 3 3 1 2 4 1 3 2 3 2 6 3 1 2 5 3 1 4 3 2 9 2 2 1 4 2 3 7 3 1 3 2 2 1 4 2 3 5

3 1 2

**MIUP'2012, 20 de Outubro, DCC/FCUP**

This document was translated from L^{A}T_{E}X byH^{E}V^{E}A.