Description

有N个单身的男孩和N个单身女孩,男孩i和女孩j在一起得到的幸福值为Hij。一个匹配即对这N个男孩女孩的安排:
每个男孩恰好有一个女朋友,每个女孩恰好有一个男朋友。一个匹配的幸福值即这N对男女朋友的幸福值的和。经
典的问题是计算幸福值最大的匹配,即完美匹配。然而完美匹配有时候并不唯一,你需要计算,对于所有的完美匹
配,其交集是什么。

Input

输入的第一行是一个正整数N。N ≤ 80
接下来是一个N*N大小的矩阵H,Hij表示男孩i和女孩j在一起的幸福值。(0≤Hij≤5000)

Output

第一行输出完美匹配的幸福值
接下来是若干行,每一行是一对整数i和j,表示男孩i和女孩j在所有完美匹配的交集中。以i的递增顺序输出

Sample Input

3
1 1 1
2 1 1
1 1 1

Sample Output

4
2 1

HINT

Source

一开始觉得暴力能过 仔细分析复杂度觉得有问题 但是还是写了T飞 然后仔细分析发现不需要n^2枚举边 只需要枚举那些有流量的边即可 然后AC

 

分类: 费用流

elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330

发表评论