大师巡回赛征服战 - 题目

Hearthstone Masters Tour 是著名集换式卡牌游戏《炉石传说》（Hearthstone）的一项赛事，每年举办多场线上及线下活动，汇集了大师资格赛的获胜者、炉石传说特级大师以及其他受邀选手，共同争夺巨额奖金。

在 Hearthstone Masters Tour 中，选手们采用“征服”（Conquest）赛制进行对决，这也是炉石传说官方赛事中采用的主要比赛赛制。该赛制的规则描述如下：

每位选手根据赛事规则携带特定数量的卡组。
在每一轮比赛开始时，双方选手各选择一套卡组与对手对战，且选择的卡组对对手保密。双方选择的卡组必须满足以下规则：
- 任何获胜的卡组在后续比赛中不能再次使用；
- 任何战败的卡组可以在后续比赛中再次使用。
随后，两位选手使用选定的卡组进行一局游戏。
率先使用完所有卡组获胜的选手赢得整场比赛。

现在，你正在参加某场 Hearthstone Masters Tour 的比赛，双方各携带 $n$ 套卡组，且卡组已确定。给定一个 $n \times n$ 的矩阵 $A$，其中 $A_{i,j}$ 表示如果你选择第 $i$ 套卡组而对手选择第 $j$ 套卡组时，你赢得该局游戏的概率。

假设你的对手了解你的策略，并且在每一轮中都会选择最优的卡组，请问你赢得整场比赛的最大概率是多少？

第一行包含一个整数 $T(1 \le T \le 5)$，表示测试用例的数量。

对于每个测试用例，第一行包含一个整数 $n(1 \le n \le 8)$，表示每位选手携带的卡组数量。

接下来 $n$ 行描述矩阵 $A$，其中第 $i(1 \le i \le n)$ 行包含 $n$ 个数字，数字最多保留两位小数，表示 $A_{i,1}, A_{i,2}, \dots, A_{i,n}(0 \le A_{i,j} \le 1)$。

对于每个测试用例，输出一行一个数字，表示答案。如果你的答案与标准答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。

形式化地，设你的答案为 $a$，标准答案为 $b$。如果 $|a - b| \min(1, |b|) \le 10^{-6}$，则你的答案被视为正确。

3
1
0.50
3
1.00 1.00 1.00
1.00 1.00 1.00
0.00 0.00 0.00
3
1.00 0.00 0.00
0.00 1.00 0.00
0.00 0.00 1.00

0.5000000000
0.0000000000
0.1666666667

对于样例中的第三个测试用例，如果你在每一轮都使用确定的策略，那么如果对手还有剩余卡组，他也会确定性地选择一套胜率为 1 的卡组。你的最优策略是在每一轮中从剩余卡组中均匀随机地选择一套，这样无论对手在每一轮选择什么策略，你赢得比赛的概率均为 $\frac{1}{6}$。

QOJ.ac