ABC371 C問題〜グラフの同型〜

ABC

解説動画

コード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (n); ++i) int main() {
    int n; cin >> n;

    vector<vector> g(n, vector(n, 0)), h(n, vector(n, 0));
    int mg;
    cin >> mg;

    rep(i, mg) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        g[u][v] = 1;
        g[v][u] = 1;
    }
    int mh;
    cin >> mh;

    rep(i, mh) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        h[u][v] = 1;
        h[v][u] = 1;
    }
    // rep(i, n) {
    //     rep(j, n) {
    //         cout << g[i][j] << " ";
    //     }
    //     cout << endl;
    // }
    // cout << "===" << endl;

    // rep(i, n) {
    //     rep(j, n) {
    //         cout << h[i][j] << " ";
    //     }
    //     cout << endl;
    // }

    vector<vector> a(n, vector(n, 0));

    rep(i, n - 1) {
        rep(j, n) {
            if (j <= i) continue; cin >> a[i][j];
        }
    }

    // rep(i, n - 1) {
    //     rep(j, n) {
    //         cout << a[i][j] << " ";
    //     }
    //     cout << endl;
    // }
    vector p(n);
    rep(i, n) p[i] = i;

    int ans = INT_MAX;
    do {
        // rep(i, n) cout << p[i] << " ";
        // cout << endl;

        int now = 0;
        rep(i, n) {
            rep(j, n) {
                if (h[i][j] != g[p[i]][p[j]]) {
                    now += a[i][j];
                }
            }
        }
        ans = min(ans, now);
    } while (next_permutation(p.begin(), p.end()));

    cout << ans << endl;

    return 0;
}

コメント