UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#4643. 卡常大水题

Statistics 下载数据

Description

这是一道卡常大水题,会做的人也不要激动,希望大家不要被卡常。
给定一张N个点的有向完全图,点的编号为1到N,每一条边有两个权值,注
意x到y的边和y到x的边的权值不一定相同。
现在你想选出一些边,使得任意两个点都可以仅经过这些边互相到达,并且
这个边集中每种权值的最大值的和尽量小。保证图中至少有两个点,因此该边集
显然不能为空。

Input

输入的第一行包括一个整数t,表示数据组数。
每组数据的第一行包括一个整数N,表示有向完全图的点数。
接下来是一个N×N的矩阵,第i行第J列的整数Aij当i=j时是0,当i≠j时表
示点i与点j之间的连边的第一种权值。
接下来是一个N×N的矩阵,第i行第j列的整数Bij当i=j时是0,当i≠j时表
示点i与点j之间的连边的第二种权值。
2 ≤ N ≤ 150, 0 ≤ Aij, Bij ≤ 10^9, Aii = Bii = 0

Output

输出一行一个整数,表示最小的和。

Sample Input

3
0 1 2
2 0 1
1 2 0
0 3 1
1 0 3
3 1 0

Sample Output

3
一种最优解是选择边1 → 3, 3 → 2, 2 → 1, 两种权值的最大值分别是2, 1
因此答案是2 + 1 = 3。

Hint

本题时限较紧,请注意尽量选择效率高的算法。

高维数组寻址的效率不高,因此优化高维数组寻址可以获得很高的效率提升。

Source