提示: 欢迎访问OurACM平台。
Problem 2233 ~APTX4869

Accept: 157    Submit: 502
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

为了帮助柯南回到一米七四,阿笠博士夜以继日地研究APTX4869的解药。他得出了如下结果:

1.解药由n种原料构成;

2.对于两种不同的的原料a,b,它们之间有个影响值f(a,b);

3.需要把原料分成两个部分X,Y,每部分中至少有一种原料;

4.解药的效果由分别属于X,Y的原料之间,最小的影响值决定,即

效果=min{f(a,b)|a∈X,b∈Y)}

博士需要你帮忙求出:在所有的方案中,最大的效果值可以是多少?

Input

多组数据(<=10),处理到EOF。

每组数据输入第一行为一个正整数n。

接下去是一个n行n列的整数矩阵,同一行的数以空格隔开。矩阵第i行j列表示第i种和第j种材料的影响值f(i,j)。给出的矩阵是对称的,即f(i,j)=f(j,i)。当i=j时,f(i,i)没有意义,矩阵该处的值为-1。

2<=n<=800。当i!=j时,0<=f(i,j)<=1000000;当i=j时,f(i,j)=-1。

Output

每组数据输出一行,表示最大可能的效果值。

Sample Input

3 -1 100 300 100 -1 200 300 200 -1

Sample Output

200

Source

福州大学第十三届程序设计竞赛

Submit  Back  Status  Discuss