P3967 [TJOI2014]匹配

    • 116通过
    • 420提交
  • 题目提供者 elijahqi
  • 评测方式 云端评测
  • 标签 二分图 枚举,暴力 费用流 各省省选 2014 天津
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    有N个单身的男孩和N个单身女孩,男孩i和女孩j在一起得到的幸福值为Hij。一个匹配即对这N个男孩女孩的安排:每个男孩恰好有一个女朋友每个女孩恰好有一个男朋友。

    一个匹配的幸福值即这N对男女朋友的幸福值的和。经典的问题是计算幸福值最大的匹配,即完美匹配。然而完美匹配有时候并不唯一,你需要计算对于所有的完美匹配,其交集是什么。

    输入输出格式

    输入格式:

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

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    3
    1 1 1
    2 1 1
    1 1 1
    输出样例#1: 复制
    4
    2 1

    说明

    数据范围

    对于 30% 的数据,N ≤ 30

    对于 100% 的数据,N ≤ 80

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。