← 返回题目列表

AtCoder · abc371_c

E. 使同构

中文机器翻译题面 查看原题

分数: 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