分数: 300 点
问题陈述
给出了简单的无向图 G 和 H,每个都有 N 顶点:顶点 1, 2, \ldots, N。 图 G 有 M_G 边缘及其 i第边缘 (1\leq i\leq M_G) 连接顶点 u_i 和 v_i。 图 H 有 M_H 边缘及其 i第边缘 (1\leq i\leq M_H) 连接顶点 a_i 和 b_i.
您可以对图表执行以下操作 H 任意次数,可能为零。
- 选择一对整数 (i,j) 满意 1\leq i<j\leq N。支付 A_{i,j} 日元,并且如果顶点之间没有边 i 和 j in H,加一;如果有,请将其删除。
找出制造所需的最低总成本 G 和 H 同构。
什么是简单无向图?
A 简单无向图 是一个没有自环或多边的图,其中边没有方向。
图同构是什么意思?
两张图 G 和 H 与 N 顶点是 同构 当且仅当存在排列 (P_1,P_2,\ldots,P_N) of (1,2,\ldots,N) 这样对于所有 1\leq i\lt j\leq N:
- 顶点之间存在边 i 和 j in G 当且仅当顶点之间存在边 P_i 和 P_j in H.
约束
- 1\leq N\leq8
- 0\leq M _ G\leq\dfrac{N(N-1)}2
- 0\leq M _ H\leq\dfrac{N(N-1)}2
- 1\leq u _ i\lt v _ i\leq N\ (1\leq i\leq M _ G)
- (u _ i,v _ i)\neq(u _ j,v _ j)\ (1\leq i\lt j\leq M _ G)
- 1\leq a _ i\lt b _ i\leq N\ (1\leq i\leq M _ H)
- (a _ i,b _ i)\neq(a _ j,b _ j)\ (1\leq i\lt j\leq M _ H)
- 1\leq A _ {i,j}\leq 10 ^ 6\ (1\leq i\lt j\leq N)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N
M _ G
u _ 1 v _ 1
u _ 2 v _ 2
\vdots
u _ {M _ G} v _ {M _ G}
M _ H
a _ 1 b _ 1
a _ 2 b _ 2
\vdots
a _ {M _ H} b _ {M _ H}
A _ {1,2} A _ {1,3} \ldots A _ {1,N}
A _ {2,3} \ldots A _ {2,N}
\vdots
A _ {N-1,N}
输出
打印答案。
示例输入 1
5 4 1 2 2 3 3 4 4 5 4 1 2 1 3 1 4 1 5 3 1 4 1 5 9 2 6 5 3
示例输出 1
9
给出的图表如下:

例如,您可以对以下四种操作进行操作: H 使其同构 G 成本为 9 日元。
- 选择 (i,j)=(1,3)。顶点之间有一条边 1 和 3 in H,所以付费 1 日元将其删除。
- 选择 (i,j)=(2,5)。顶点之间没有边 2 和 5 in H,所以付费 2 日元添加它。
- 选择 (i,j)=(1,5)。顶点之间有一条边 1 和 5 in H,所以付费 1 日元将其删除。
- 选择 (i,j)=(3,5)。顶点之间没有边 3 和 5 in H,所以付费 5 日元添加它。
这些操作之后, H 变为:

你不能 G 和 H 同构,成本低于 9 日元,所以打印 9.
示例输入 2
5 3 1 2 2 3 3 4 4 1 2 2 3 3 4 4 5 9 1 1 1 1 1 1 1 1 9
示例输出 2
3
例如,执行以下操作 (i,j)=(2,3),(2,4),(3,4) on H 将使其同构 G.
示例输入 3
5 3 1 2 2 3 3 4 4 1 2 2 3 3 4 4 5 5 4 4 4 4 4 4 4 4 5
示例输出 3
5
例如,执行操作 (i,j)=(4,5) 一次就会使 G 和 H 同构。
示例输入 4
2 0 0 371
示例输出 4
0
请注意 G 和 H 可能没有边缘。
此外,也可能不需要任何操作。
示例输入 5
8 13 1 8 5 7 4 6 1 5 7 8 1 6 1 2 5 8 2 6 5 6 6 7 3 7 4 8 15 3 5 1 7 4 6 3 8 7 8 1 2 5 6 1 6 1 5 1 4 2 8 2 6 2 4 4 7 1 3 7483 1694 5868 3296 9723 5299 4326 5195 4088 5871 1384 2491 6562 1149 6326 2996 9845 7557 4041 7720 1554 5060 8329 8541 3530 4652 3874 3748
示例输出 5
21214