TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2108
  • 题目
  • P2108【并查集】Ali的乐谱
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    阿狸被邀请参加钢琴晚会咯,为了在晚会上展现自己的雄姿,阿狸打算自己谱曲。
    阿狸的曲子中有N个音节,阿狸要将他们分成K组,来组成不同的音乐片段。在这些音节中,每两个音节之间有一个美妙值。当然,两个音节之间的美妙值是相同的,比如A对B的美妙值等于B对A的美妙值。
    我们这样定义两个音乐片段之间的美妙值:假如第一组有x 个音符,第二组有y个音符,则两组中的每对音符之间分别有一个美妙值,那么一共有x*y个美妙值。这两个音乐片段之间的美妙值就是这x*y个美妙值中最小的那一个。
    比如考虑如下分组:
    (A,B) 和(C,D) 一共有2*2=4 个美妙值,若A−C美妙值为3,A−D 美妙值为2,B−C美妙值为1,B−D美妙值为4,则(A,B) 组和(C,D)组配对的美妙值为min{3,2,1,4}=1。
    阿狸希望分好之后的所有组之间,组与组的最小美妙值尽可能大,由于它还要花时间练习基本功,所以他想请你为他安排出最美妙的乐谱。
    阿狸很聪明的,你只需要输出满足阿狸愿望的乐谱的美妙值即可。

    输入格式

    第1 行为两个整数K,N,为音乐片段的组数和音符的个数。
    第2 行开始有一个N*N的整数矩阵, 第i+1行第j列表示第i个音符与第j个音符之间的美妙值。注意同一个音符与自己不存在美妙值, 所以第i+1 行第i列均为0 。

    输出格式

    第1 行为一个整数, 为满足阿狸愿望的最大美妙值。

    样例输入

    2 3
    0 1 2
    1 0 2
    2 2 0

    样例输出

    2

    提示

    N≤ 1000 ,2 ≤K ≤N , 矩阵中的数≤ 1000000000


    来源  hzoi