stable marriage problem happiness coefficient

Question

I am trying to solve this problem for an online judge:

There are sets of n men and n women. Each man evaluates the women with numbers from 1 to n, giving them different grades, and each woman estimates similarly to the men from 1 to n. This all leads to formation of pairs according to the principle of maximum attractiveness for both partners and calculation of the happiness coefficient. The coefficient of happiness is the sum of the man's evaluation and the evaluation of the woman.

You have to maximize the sum of the happiness coefficients of the pairs and to output these pairs.

Input:

The first line contains a natural n where 1  ≤  n ≤ 1000 – the quantity of people of the same sex.

The next n lines contain men’s evaluations for each of the women.

The final n lines for women are input analogically.

Output:

The first line should contain the maximal sum of the happiness coefficients of the pairs.

The second line should contain men’s partners successively (firstly, the partner for the first man, then the partner for the second man, and so on).

Example:

Input

3
1 2 3
2 3 1
1 2 3
1 2 3
2 3 1
3 1 2

Output

16
3 2 1

I have the following code:

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

void stable_marriage(vector<vector<int>> &matrix) {
    int n = matrix[0].size();
    vector<int> status(n * 2, -1);/*status[i] contains husband/wife of i, initially -1*/
    queue<int> q;
    for (int i = 0; i < n; i++)/* Push all single men */
        q.push(i);
    /* While there is a single men */
    while (!q.empty()) {
        int i = q.front();
        q.pop();
        /* iterate through his preference list */
        for (int j = 0; j < n; j++) {
            /* if girl is single marry her to this man*/
            if (status[matrix[i][j]] == -1) {
                status[i] = matrix[i][j];/* set this girl as wife of i */
                status[matrix[i][j]] = i;/*make i as husband of this girl*/
                break;
            }
            else {
                int rank_1, rank_2;/* for holding priority of current husband and most preferable husband*/
                for (int k = 0; k < n; k++) {
                    if (matrix[matrix[i][j]][k] == status[matrix[i][j]])
                        rank_1 = k;
                    if (matrix[matrix[i][j]][k] == i)
                        rank_2 = k;
                }
                /* if current husband is less attractive
                than divorce him and marry a new one making the old one
                single */
                if (rank_2 < rank_1) {/* if this girl j prefers current man i 
                                        more than her present husband */
                    status[i] = matrix[i][j];/* her wife of i */
                    int old = status[matrix[i][j]];
                    status[old] = -1;/*divorce current husband*/
                    q.push(old);/*add him to list of singles */
                    status[matrix[i][j]] = i;/* set new husband for this girl*/
                    break;
                }
            }
        }
    }
    for (int i = n - 1; i >= 0; i--) {
        cout << status[i] << ' ';
    }
}
int main() {

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    int n;
    cin >> n;
    vector<vector<int>> matrix(n * 2, vector<int>(n));
    for (int i = 0; i < n * 2; i++) {
        for (int j = 0; j < n; j++) {
            cin >> matrix[i][j];
        }
    }

    stable_marriage(matrix);
    return 0;
}

Now, what I don't get is that how the happiness coefficient is measured? I don't see how, can you help?

Answer 1

The problem states that the happiness for a couple is the sum of their evaluations for their respective partners. The value you are supposed to find is the maximum value of the sum of happiness for the n couples that can be formed with the given men and women.

For instance, for the sample input, the following pairings are possible.

A = (1, 1), (2, 2), (3, 3)
B = (1, 1), (2, 3), (3, 2)
C = (1, 2), (2, 1), (3, 3)
D = (1, 2), (2, 3), (3, 1)
E = (1, 3), (2, 2), (3, 1)
F = (1, 3), (2, 1), (3, 2)

As you can confirm by manually calculating their evaluations of one another, the following are the sums that can be obtained for each scenario.

A = ( 2 + 6 + 5 ) = 13
B = ( 2 + 2 + 3 ) = 7
C = ( 4 + 4 + 5 ) = 13
D = ( 4 + 2 + 4 ) = 10
E = ( 6 + 6 + 4 ) = 16
F = ( 6 + 4 + 3 ) = 13

As you can see, the maximum amount of total happiness that can be achieved is 16, as given in the sample output.