C - Make Isomorphic

Contest Duration: 2024-09-14(Sat) 12:00 - 2024-09-14(Sat) 13:40 (local time) (100 minutes) Back to Home

C - Make Isomorphic Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $300$ 点

問題文

頂点 $1,$ 頂点 $2,\ldots,$ 頂点 $N$ の $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$ 回以上の好きな回数繰り返すことができます。

$1\leq i\lt j\leq N$ を満たす整数の組 $(i,j)$ をひとつ選ぶ。 $A _ {i,j}$ 円を支払って、頂点 $i$ と頂点 $j$ を結ぶ辺がなければ追加し、あれば取り除く。

$G$ と $H$ を同型にするために少なくとも何円支払う必要があるか求めてください。

単純無向グラフとは？

単純無向グラフとは、自己ループや多重辺を含まず、辺に向きの無いグラフのことをいいます。

グラフの同型とは？

$N$ 頂点のグラフ $G$ と $H$ が同型であるとは、ある $(1,2,\ldots,N)$ の並べ替え $(P _ 1,P _ 2,\ldots,P _ N)$ が存在して、どの $1\leq i\lt j\leq N$ に対しても

$G$ に頂点 $i,$ 頂点 $j$ を結ぶ辺が存在するとき、かつそのときに限り $H$ に頂点 $P _ i,$ 頂点 $P _ j$ を結ぶ辺が存在する

が成り立つことをいいます。

制約

$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}$

出力

答えを出力せよ。

入力例 1Copy

Copy

出力例 1Copy

Copy

与えられたグラフはそれぞれ以下のようになります。

たとえば、 $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 を出力してください。

入力例 2Copy

Copy

出力例 2Copy

Copy

たとえば、 $(i,j)=(2,3),(2,4),(3,4)$ とした $3$ 回の操作を行うことで $G$ と $H$ を同型にすることができます。

入力例 3Copy

Copy

出力例 3Copy

Copy

たとえば、 $(i,j)=(4,5)$ とした $1$ 回の操作を行うことで $G$ と $H$ を同型にすることができます。

入力例 4Copy

Copy

出力例 4Copy

Copy

$G$ や $H$ には辺が含まれていないこともあります。また、一度も操作をする必要がないこともあります。

入力例 5Copy

Copy

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

出力例 5Copy

Copy

Score : $300$ points

Problem Statement

You are given simple undirected graphs $G$ and $H$ , each with $N$ vertices: vertices $1$ , $2$ , $\ldots$ , $N$ . Graph $G$ has $M_G$ edges, and its $i$ -th edge $(1\leq i\leq M_G)$ connects vertices $u_i$ and $v_i$ . Graph $H$ has $M_H$ edges, and its $i$ -th edge $(1\leq i\leq M_H)$ connects vertices $a_i$ and $b_i$ .

You can perform the following operation on graph $H$ any number of times, possibly zero.

Choose a pair of integers $(i,j)$ satisfying $1\leq i<j\leq N$ . Pay $A_{i,j}$ yen, and if there is no edge between vertices $i$ and $j$ in $H$ , add one; if there is, remove it.

Find the minimum total cost required to make $G$ and $H$ isomorphic.

What is a simple undirected graph?

A simple undirected graph is a graph without self-loops or multi-edges, where edges have no direction.

What does it mean for graphs to be isomorphic?

Two graphs $G$ and $H$ with $N$ vertices are isomorphic if and only if there exists a permutation $(P_1,P_2,\ldots,P_N)$ of $(1,2,\ldots,N)$ such that for all $1\leq i\lt j\leq N$ :

an edge exists between vertices $i$ and $j$ in $G$ if and only if an edge exists between vertices $P_i$ and $P_j$ in $H$ .

Constraints

$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)$
All input values are integers.

Input

The input is given from Standard Input in the following format:

 $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}$

Output

Print the answer.

Sample Input 1Copy

Copy

Sample Output 1Copy

Copy

The given graphs are as follows:

For example, you can perform the following four operations on $H$ to make it isomorphic to $G$ at a cost of $9$ yen.

Choose $(i,j)=(1,3)$ . There is an edge between vertices $1$ and $3$ in $H$ , so pay $1$ yen to remove it.
Choose $(i,j)=(2,5)$ . There is no edge between vertices $2$ and $5$ in $H$ , so pay $2$ yen to add it.
Choose $(i,j)=(1,5)$ . There is an edge between vertices $1$ and $5$ in $H$ , so pay $1$ yen to remove it.
Choose $(i,j)=(3,5)$ . There is no edge between vertices $3$ and $5$ in $H$ , so pay $5$ yen to add it.

After these operations, $H$ becomes:

You cannot make $G$ and $H$ isomorphic at a cost less than $9$ yen, so print 9.

Sample Input 2Copy

Copy

Sample Output 2Copy

Copy

For example, performing the operations $(i,j)=(2,3),(2,4),(3,4)$ on $H$ will make it isomorphic to $G$ .

Sample Input 3Copy

Copy

Sample Output 3Copy

Copy

For example, performing the operation $(i,j)=(4,5)$ once will make $G$ and $H$ isomorphic.

Sample Input 4Copy

Copy

Sample Output 4Copy

Copy

Note that $G$ and $H$ may have no edges.

Also, it is possible that no operations are needed.

Sample Input 5Copy

Copy

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

Sample Output 5Copy

Copy