匹配
测试数据来自 system/1858
描述
有 N 个单身的男孩和 N 个单身女孩,男孩 i 和女孩 j 在一起得到的幸福值为 Hij。一个匹配即对这 N 个男孩女孩的安排:每个男孩恰好有一个女朋友,每个女孩恰好有一个男朋友。
一个匹配的幸福值即这 N 对男女朋友的幸福值的和。经典的问题是计算幸福值最大的匹配,即完美匹配。然而完美匹配有时候并不唯一,你需要计算,对于所有的完美匹配,其交集是什么。
格式
输入格式
输入的第一行是一个正整数 N。接下来是一个 N ∗ N 大小的矩阵 H,Hij 表示男孩 i 和女孩 j 在一起的幸福值。(0 ≤ Hij ≤ 5000)
输出格式
第一行输出完美匹配的幸福值,接下来是若干行,每一行是一对整数 i 和 j,表示男孩 i 和女孩 j 在所有完美匹配的交集中。以 i 的递增顺序输出。
样例1
样例输入1
3
1 1 1
2 1 1
1 1 1
样例输出1
4
2 1
限制
对于 30% 的数据,N ≤ 30
对于 100% 的数据,N ≤ 80
来源
天津2014 day1
信息
- ID
- 1791
- 难度
- (无)
- 分类
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 通过率
- ?
- 上传者