まず、同じ \((i,j)\) に対して \(2\) 回以上操作をする意味はありません。 よって、それぞれの \((i,j)\) に対しては \(0\) 回操作するか \(1\) 回操作するかのどちらかです。

\(H\) の各頂点が \(G\) のどの頂点に対応するかを固定することで、\((i,j)\) に対して操作すべき回数がわかります。 よって、この対応について考えると次の問題に言い換えることができます。

\(P\) が \((1,2,\ldots,N)\) の並べ替えすべてをわたるとき、「\(G\) に辺 \((P _ i,P _ j)\) が含まれるか」と「\(H\) に辺 \((i,j)\) が含まれるか」が異なる \(i,j\) に対する \(A _ {i,j}\) の総和の最小値を求めよ。

この問題の制約で \(N\leq8\) なので、ありえる \(P\) はたかだか \(40320\) 通りです。 それぞれに対して、ありえる辺 \((i,j)\ (1\leq i\lt j\leq N)\) を \(\dfrac{N(N-1)}2\) 通りすべて確かめ、総和を計算しても十分高速です。

並べ替えすべてを列挙するためには、再帰関数を使ったり、C++ などでは std::next_permutation などの標準で用意されている関数を使ったりすることができます。

実装例は以下のようになります。

以下の実装例では、グラフに辺が含まれているかを std::set を用いて判定しているため、全体の計算量は \(\Theta(N!\,N ^ 2\log N)\) となっています。

#include <iostream>
#include <set>
#include <utility>
#include <vector>
#include <numeric>
#include <algorithm>

int main() {
    using namespace std;
    int N;
    cin >> N;

    // グラフ G, H に含まれる辺の集合
    set<pair<int, int>> edges_G, edges_H;
    
    int M_G;
    cin >> M_G;
    for (int i = 0; i < M_G; ++i) {
        int u, v;
        cin >> u >> v;
        edges_G.emplace(u - 1, v - 1);
        edges_G.emplace(v - 1, u - 1); // 逆向きの辺も追加しておく
    }
    
    int M_H;
    cin >> M_H;
    for (int i = 0; i < M_H; ++i) {
        int a, b;
        cin >> a >> b;
        edges_H.emplace(a - 1, b - 1);
        edges_H.emplace(b - 1, a - 1); // 逆向きの辺も追加しておく
    }

    vector A(N, vector<int>(N));
    for (int i = 0; i < N; ++i) {
        for (int j = i + 1; j < N; ++j) {
            cin >> A[i][j];
            A[j][i] = A[i][j]; // 逆向きのコストも追加しておく
        }
    }

    // H の頂点を G の頂点に対応させる並べ替え
    vector<int> P(N);
    iota(begin(P), end(P), 0);

    int ans{28000000}; // 答えは 8 * (8 - 1) / 2 * 10^6 以下
    
    // すべての並べ替えを探索
    do {
        int sum = 0;
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < i; ++j) {
                // H に (i, j) が含まれて G に (P[i], P[j]) が含まれない か、
                // H に (i, j) が含まれずに G に (P[i], P[j]) が含まれる 場合 A[i][j] を足す
                sum += A[i][j] * (edges_H.contains({i, j}) != edges_G.contains({P[i], P[j]}));
            }
        }
        // 最小値を更新
        ans = min(ans, sum);
    } while(ranges::next_permutation(P).found);

    cout << ans << endl;
    return 0;
}