P3967 [TJOI2014] Matching

There are $N$ single boys and $N$ single girls. The happiness of pairing boy $i$ with girl $j$ is $H_{i,j}$. A matching is an arrangement of these $N$ boys and girls such that each boy has exactly one girlfriend and each girl has exactly one boyfriend. The happiness of a matching is the sum of the happiness values of these $N$ pairs. The classic task is to compute the maximum possible happiness, i.e., a maximum-weight perfect matching (also called an "assignment"). However, the maximum-weight perfect matching is not always unique. You need to compute the intersection of all maximum-weight perfect matchings.

The first line contains a positive integer $N$. Then follows an $N \times N$ matrix $H$, where $H_{i,j}$ denotes the happiness of pairing boy $i$ with girl $j$.

On the first line, output the happiness of the maximum-weight perfect matching. Then output several lines, each containing a pair of integers $i$ and $j$, indicating that boy $i$ and girl $j$ appear in the intersection of all maximum-weight perfect matchings, in increasing order of $i$.

- For 30% of the testdata, $N \leq 30$. - For 100% of the testdata, $1 \leq N \leq 80$, $0 \leq H_{i,j} \leq 5 \times 10^3$. Translated by ChatGPT 5