AT_abc371_c [ABC371C] Make Isomorphic

题目描述

给定一个包含 $N$ 个顶点（顶点 $1,2,\ldots,N$）的简单无向图 $G$ 和 $H$。$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$ 重复进行如下操作任意次（可以为 $0$ 次）：

• 选择一组整数 $(i,j)$，满足 $1\leq i<j\leq N$。支付 $A_{i,j}$ 日元，如果顶点 $i$ 和顶点 $j$ 之间没有边，则添加一条边；如果已经有边，则删除该边。

请你求出，为了使 $G$ 和 $H$ 同构，至少需要支付多少日元。

什么是简单无向图？简单无向图是指不包含自环和重边，且边没有方向的图。

什么是图的同构？对于 $N$ 个顶点的图 $G$ 和 $H$，如果存在一个排列 $(P_1,P_2,\ldots,P_N)$，使得对于任意 $1\leq i<j\leq N$，有：

• 当且仅当 $G$ 中存在连接顶点 $i$ 和顶点 $j$ 的边时，$H$ 中存在连接顶点 $P_i$ 和顶点 $P_j$ 的边，

则称 $G$ 和 $H$ 是同构的。

输入格式

输入以如下格式从标准输入读入。

$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

输入 #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

输入输出样例 #2

输入 #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

输入输出样例 #3

输入 #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

输入输出样例 #4

输入 #4

2
0
0
371

输出 #4

0

输入输出样例 #5

输入 #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

说明/提示

数据范围

• $1\leq N\leq 8$
• $0\leq M_G\leq\dfrac{N(N-1)}{2}$
• $0\leq M_H\leq\dfrac{N(N-1)}{2}$
• $1\leq u_i<v_i\leq N\ (1\leq i\leq M_G)$
• $(u_i,v_i)\neq(u_j,v_j)\ (1\leq i<j\leq M_G)$
• $1\leq a_i<b_i\leq N\ (1\leq i\leq M_H)$
• $(a_i,b_i)\neq(a_j,b_j)\ (1\leq i<j\leq M_H)$
• $1\leq A_{i,j}\leq 10^6\ (1\leq i<j\leq N)$
• 输入均为整数

样例解释 1

给定的图如下所示。

例如，可以对 $H$ 依次进行如下 $4$ 次操作，支付 $9$ 日元使 $G$ 和 $H$ 同构：

• 以 $(i,j)=(1,3)$ 进行操作。$H$ 中有顶点 $1$ 和 $3$ 的边，支付 $1$ 日元将其删除。
• 以 $(i,j)=(2,5)$ 进行操作。$H$ 中没有顶点 $2$ 和 $5$ 的边，支付 $2$ 日元将其添加。
• 以 $(i,j)=(1,5)$ 进行操作。$H$ 中有顶点 $1$ 和 $5$ 的边，支付 $1$ 日元将其删除。
• 以 $(i,j)=(3,5)$ 进行操作。$H$ 中没有顶点 $3$ 和 $5$ 的边，支付 $5$ 日元将其添加。

操作后，$H$ 如下所示。

无法用 $8$ 日元或更少使 $G$ 和 $H$ 同构，因此输出 9。

样例解释 2

例如，依次对 $(i,j)=(2,3),(2,4),(3,4)$ 进行 $3$ 次操作即可使 $G$ 和 $H$ 同构。

样例解释 3

例如，仅对 $(i,j)=(4,5)$ 进行 $1$ 次操作即可使 $G$ 和 $H$ 同构。

样例解释 4

$G$ 和 $H$ 也可能都没有边。也有可能不需要进行任何操作。

由 ChatGPT 4.1 翻译