[TJOI2014]匹配 - 题目 - Universal Online Judge

## 题目描述有

$N$ 个单身的男孩和

$N$ 个单身女孩，男孩

$i$ 和女孩

$j$ 在一起得到的幸福值为

$H_{i,j}$ 。一个匹配即对这

$N$ 个男孩女孩的安排：每个男孩恰好有一个女朋友，每个女孩恰好有一个男朋友。一个匹配的幸福值即这

$N$ 对男女朋友的幸福值的和。经典的问题是计算幸福值最大的匹配，即完美匹配。然而完美匹配有时候并不唯一，你需要计算对于所有的完美匹配，其交集是什么。 ## 输入输出格式 ### 输入格式输入的第一行是一个正整数

$N$ 。接下来是一个

$N imes N$ 大小的矩阵

$H$ ，

$H_{i,j}$ 表示男孩

$i$ 和女孩

$j$ 在一起的幸福值。 ### 输出格式第一行输出完美匹配的幸福值，接下来是若干行，每一行是一对整数

$i$ 和

$j$ ，表示男孩

$i$ 和女孩

$j$ 在所有完美匹配的交集中，以

$i$ 的递增顺序输出。 ## 输入输出样例 ### 输入样例 #1 ``` 3 1 1 1 2 1 1 1 1 1 ``` ### 输出样例 #1 ``` 4 2 1 ``` ## 说明/提示 - 对于

$30\%$ 的数据，

$N leq 30$ ； - 对于

$100\%$ 的数据，

$1leq N leq 80$ ，

$0leq H_{i,j}leq 5 imes10^3$ 。

Universal Online Judge