蓝桥杯软件赛模拟练习二（C++ & Python）

104418. 学院交流【算法赛】

问题描述

蓝桥学院计划派遣 N 名同学前往 A 学院和 B 学院进行程序设计交流活动。每位同学必须且仅能被分配到其中一所学院，且每所学院至少需分配一名同学。

对于任意两位同学 i 和 j（i≠j），如果他们被分配到同一所学院，则会产生化学反应值 Si,j（一个正整数）。

一种分配方案的团队化学反应值定义为：在同一学院的所有不同同学对之间的化学反应值的最小值。如果某学院只有一人，则该学院无化学反应值贡献，整体团队化学反应值由另一学院决定。

请找出所有可能分配方案中，能够达到的最大团队化学反应值。

输入格式

第一行包含一个整数 N（3≤N≤500），表示同学的数量。

接下来 N 行，每行包含 N 个整数，其中第 i行第 j 列的数为 Si,j（若 i=j，则 Si,i=0；否则 1≤Si,j≤1e9，且 Si,j