実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 849

問題概要

$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回以上繰り返して $G$ と $H$ を同型にすることを考える。

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

このとき、少なくとも何円が必要かどうか求めよ。

制約

入力はすべて整数。
$1 \leq N \leq 8$
$0 \leq M_G, M_H \leq \frac{N(N-1)}{2}$
$1 \leq u_i \lt v_i \leq N \: (1 \leq i \leq M_G)$
$1 \leq a_i \lt b_i \leq N \: (1 \leq i \leq M_H)$
$1 \leq A_{i, j} \leq 10^6$

考察

まずは $N$ の制約がとても小さいことに注目したい。

また、グラフが同型になるためには各頂点の結合関係が等しくなれば良いので、「 $H$ の各頂点を $G$ のどの頂点に対応させるかを順列全探索する」という方針が立てられそう。このような場合の数は $N!$ 通りなので、高々 $8! = 40320$ 通りである。

そして、各順列に対して辺 $(i, j)$ の選び方 $\frac{N(N-1)}{2}$ 通りを全探索して、 $G$ と $H$ で辺の存在状況が異なるならば、 $A_{i, j}$ 円を支払って $G$ に合わせることとする。

コードでは、グラフの辺の存在を簡単に行えるように、隣接行列をデータ構造として採用している。

コード

#include <bits/stdc++.h>
using namespace std;

#define all(x) (x).begin(), (x).end()
#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

constexpr auto INF = 1e+9;

template <typename T>
inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }

// ======================================== //

int main()
{
    int N;
    cin >> N;

    int M_G;
    cin >> M_G;
    vector<vector<bool>> G(N, vector<bool>(N, false));
    rep(i, 0, M_G)
    {
        int u, v;
        cin >> u >> v;
        u--, v--;
        G[u][v] = G[v][u] = true;
    }

    int M_H;
    cin >> M_H;
    vector<vector<bool>> H(N, vector<bool>(N, false));
    rep(i, 0, M_H)
    {
        int a, b;
        cin >> a >> b;
        a--, b--;
        H[a][b] = H[b][a] = true;
    }


    vector<vector<int>> A(N, vector<int>(N));
    rep(i, 0, N) rep(j, i + 1, N) cin >> A[i][j];

    vector<int> order(N);
    iota(all(order), 0);

    int ans = INF;
    
    do
    {
        int sum = 0;
        rep(i, 0, N) rep(j, i + 1, N)
        {
            if (G[order[i]][order[j]] != H[i][j])
            {
                sum += A[i][j];
            }
        }

        chmin(ans, sum);
    } while (next_permutation(all(order)));
    
    cout << ans << endl;
}