【競技プログラミング】AtCoder Beginner Contest 371_C問題

# 問題
https://atcoder.jp/contests/abc371/tasks/abc371_c

# 既存投稿一覧ページへのリンク
[一覧ページ](https://qiita.com/o_chan_t/items/fc759695acfaef8df2cc)

## Next
[AtCoder Beginner Contest 371_D問題](https://qiita.com/o_chan_t/items/f9ed4a01a3125500acab)

# 解法イメージ

下記のグラフを同型にすれば良いので、まずは頂点番号を付けて同型にするためのコストを算出する。
その後、全パターンの組み合わせで最小コストのものを割り出す形ですね。
![base_image.create_20250418065708.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/530912/fda253d4-5d5a-41ba-8462-b43791095694.png)


# 解法手順1

## 1. 入力データの処理
まず、入力から以下の情報を取得する
- グラフ $ G $ の辺情報 ($ edge\_G $)。
- グラフ $ H $ の辺情報 ($ edge\_H $)。
- 辺を追加または削除する際のコスト行列 ($ cost\_{matrix} $)。

これらのデータは関数 `io_func()` によって処理される。  

具体的には以下の形式でデータが格納される。
- `edge_G` および `edge_H` は隣接行列として表現され、頂点間に辺がある場合は `True`、ない場合は `False`。
- `cost_matrix[i][j]` は頂点 $ i $ と $ j $ の間で操作を行う際のコスト。

---

## 2. 全ての頂点順列を試す
次に、頂点の順列を試してグラフ $ H $ を変換する。  

### 順列について
- 順列によって、グラフ $ H $ の頂点番号を対応させることで、グラフ $ G $ と比較します。

### コスト計算
各順列について以下を行います：
1. 順列に基づいてグラフ $ H $ を変換。
2. 頂点ペア $ (i, j) $ ごとに、$ edge_G[p[i]][p[j]] \neq edge_H[i][j] $ の場合、コストを加算。
   - つまり、グラフ構造が一致しない部分について操作コストを計算する。
3. 現在の順列で得られたコストが最小値より小さい場合、それを更新する。

この処理によって、全ての可能な対応関係を考慮した上で最小コストが求められる。


## 解法の流れまとめ
1. **入力処理**:
   - グラフ情報とコスト行列を読み取る。
2. **全順列探索**:
   - 頂点番号の並べ替えによる全ての対応関係を試す。
3. **コスト計算**:
   - グラフ構造が一致しない部分について操作コストを加算。
4. **最小値更新**:
   - 各順列で得られたコストから最小値を選択する。
5. **結果出力**:
   - 最小コストを出力する。

# メモ
問題の解法を思いつくためのステップ。

## **1. 問題の本質**
まず、問題文から、以下の点を読み取る
- **目標**: グラフ $ G $ と $ H $ を同型にするための最小コストを求める。
- **操作**: 頂点ペア $ (i, j) $ の辺を追加または削除し、そのコストが与えられる。
- **制約**: グラフ同型とは、頂点の対応関係が存在し、辺の接続状態が一致すること。

この段階で、「頂点の対応関係を試行しながらコストを計算する必要がある」と理解する。

---

## **2. 解法の方向性を検討する**
- 頂点の対応関係（順列）を試す。
- 対応関係に基づいて、グラフ $ H $ を変換して $ G $ と比較する。
- 不一致部分についてコストを計算し、最小値を求める。

このとき、「全ての頂点順列を試す」という発想は、グラフ同型性の定義から自然に導かれる。 
また、「不一致部分のコスト計算」は問題文で与えられた操作条件に基づく。

---

## **3. 順列全探索という手法に気づく**
グラフ同型性の問題では、頂点間の対応関係（順列）を試すことが基本的なアプローチ。  
- 順列は $ N! $ 通り存在するため、小規模な $ N $ に対しては全探索が可能。
- 各順列について、辺の一致・不一致を確認し、不一致部分のコストを加算する。

このような「順列全探索 + コスト計算」という手法は、グラフ同型性や組合せ最適化問題で一般的なもの。

---

## **4. コスト計算方法を具体化する**
次に、不一致部分について具体的なコスト計算方法を考えます：
1. 順列 $ P $ に基づいて、グラフ $ H $ を変換。
2. 辺 $ (i, j) $ ごとに、$ edge\_G[P[i]][P[j]] \neq edge\_H[i][j] $ を確認。
3. 不一致の場合、コスト行列 $ cost\_matrix[i][j] $ の値を加算。

## **まとめ**
この解法は以下のような流れで思いつく
1. 問題文から「頂点間対応関係（順列）の全探索」が必要と判断。
2. グラフ同型性と操作条件から「不一致部分のコスト計算」を具体化。
3. 計算量や実装可能性から「順列全探索 + コスト計算」が有効と判断。


# ACコード1
```python:ac.py
import itertools
import logging

# ロガーのセットアップ
def setup_logger(debug_mode):
    logger = logging.getLogger(__name__)
    if not logger.handlers:  # ハンドラが存在しない場合のみ追加
        logger.setLevel(logging.DEBUG if debug_mode else logging.INFO)
        formatter = logging.Formatter('%(asctime)s - %(name)s - %(levelname)s - %(message)s')
        
        file_handler = logging.FileHandler('program_trace.log', encoding="utf8")
        file_handler.setFormatter(formatter)
        logger.addHandler(file_handler)
    
    logger.debug(f"ロガーのセットアップが完了しました。デバッグモード: {debug_mode}")
    return logger

# 標準入力を処理する関数
def io_func():
    n = int(input())
    mg = int(input())
    edge_G = [[False for _ in range(n)] for _ in range(n)]
    for _ in range(mg):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        edge_G[u][v] = True
        edge_G[v][u] = True
    
    mh = int(input())
    edge_H = [[False for _ in range(n)] for _ in range(n)]
    for _ in range(mh):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        edge_H[a][b] = True
        edge_H[b][a] = True
    
    cost_matrix = [[0 for _ in range(n)] for _ in range(n)]
    for i in range(n - 1):
        row = list(map(int, input().split()))
        for j, cost in enumerate(row):
            cost_matrix[i][i + j + 1] = cost
            cost_matrix[i + j + 1][i] = cost
    
    return n, edge_G, edge_H, cost_matrix

# 問題を解く関数
def solve(n, edge_G, edge_H, cost_matrix, logger):
    INF = 1 << 30
    result = INF

    # 全ての頂点の順列を試す
    for permutation in itertools.permutations(range(n)):
        cost = 0
        logger.debug(f"現在の順列: {permutation}")
        
        # 順列に基づいてコスト計算
        for i in range(n):
            for j in range(i + 1, n):
                if edge_G[permutation[i]][permutation[j]] != edge_H[i][j]:
                    cost += cost_matrix[i][j]
                    logger.debug(f"辺 ({i}, {j}) の不一致: コスト {cost_matrix[i][j]} を加算 (累積コスト: {cost})")
        
        result = min(result, cost)
        logger.debug(f"現在の最小コスト: {result}")
    
    print(result)

# メイン関数
def main():
    debug_mode = False  # 必要に応じてTrueに変更可能
    logger = setup_logger(debug_mode)
    
    # 入力処理
    n, edge_G, edge_H, cost_matrix = io_func()
    
    # 問題解決
    solve(n, edge_G, edge_H, cost_matrix, logger)

if __name__ == "__main__":
    main()


```