3073. [POJ 2288]岛和桥

【题目描述】

给定一个地图，地图中包含很多岛和连接它们的桥。

汉密尔顿路径是指沿着桥访问每个岛屿恰好一次的路径。

在我们的地图上的每个岛都具有一个权值，它是一个正整数。

假设一共有 n 个岛，第 i 个岛的权值为Vi。

现在规定一个汉密尔顿路径的总价值为以下三个价值的和：

1.每个岛屿的权值之和。

2.汉密尔顿路径中，每一条边连接的相邻岛屿的权值乘积之和。

3.如果在汉密尔顿路径中存在相邻的三个岛屿可以构成环形，则将所有满足条件的相邻岛屿三元组权值的乘积相加求和。

任务一：请你找出汉密尔顿路径的总价值最大可以为多少。

任务二：请你找出满足最大总价值的汉密尔顿路径共有多少条。

【输入格式】

第一行包含整数 q，表示共有 q 组测试数据。

每组数据第一行包含两个整数 n,m，分别表示小岛数和桥数。

第二行包含 n 个不超过100的正整数，表示每个岛屿的权值。

接下来 m 行，每行包含两个整数 a,b，表示岛 a 和岛 b 之间存在一个双向桥。

岛屿的编号从 1 到 n。

【输出格式】

每组数据输出一行，两个整数，分别表示汉密尔顿路径的最大总价值，以及满足最大总价值的汉密尔顿路径条数。

如果不存在汉密尔顿路径，则输出0 0。

注意：将一条路径按相反的顺序输出而成的路径，视为与原路径是同一条路径。例如 1-2-3 和 3-2-1 为同一条路径。

【样例输入】

2
3 3
2 2 2
1 2
2 3
3 1
4 6
1 2 3 4
1 2
1 3
1 4
2 3
2 4
3 4

【样例输出】

22 3
69 1

【数据规模与约定】

$1\leq n\leq 13,1\leq m\leq \frac{n(n-1)}{2}$