【AtCoder】ABC 396 D - Minimum XOR Path | 緑コーダーが解くAtCoder

配点: 400 点 / 実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 601

問題概要
制約
考察
実装例
コメント

問題概要

頂点に $1$ から $N$ の、辺に $1$ から $M$ の番号がついた $N$ 頂点 $M$ 辺の単純連結無向グラフが与えられる。辺 $i$ は頂点 $u_i$ と頂点 $v_i$ を結んでおり、ラベル $w_i$ が付けられている。

頂点 $1$ から頂点 $N$ への単純パスのうち、パスに含まれる辺につけられたラベルの総 XOR としてあり得る最小値を求めよ。

制約

$2\leq N\leq 10$
$N-1\leq M\leq \frac{N(N-1)}{2}$
$0\leq w_i\lt 2^{60}$
入力は全て整数。

考察

まず、 $N$ の制約が非常に小さいことに注目しよう。

グラフ上の辺数が最も大きくなるのは、与えられたグラフが完全グラフになるときで、このときの辺数は $\frac{N(N-1)}{2}$ である。

理由(クリックで展開)

完全グラフとは「どの2点の間にも辺があるような単純グラフ」のことであるが、これは言い換えれば「自身以外の $n-1$ 個の頂点すべてと辺で接続している」ということになる。

したがって、1つの頂点からは $n-1$ 個の辺が出ていることになり、無向辺による重複を考慮すると、 $n$ 頂点の完全グラフの辺数は $\frac{n(n-1)}{2}$ 本となる。

このとき、任意の頂点から他の頂点へ行くことが可能になる。

頂点 $1$ から、頂点 $1$ 以外の頂点(頂点 $i$ とする)への行き方は $N-1$ 通り。
頂点 $i$ から、頂点 $1, i$ 以外の頂点(頂点 $j$ とする)への行き方は $N-2$ 通り。

... という風に考えると、頂点 $1$ から頂点 $N$ までの単純パスは $(N-1)!$ 通りであり、最大でも $362880$ 通り。これなら十分に全探索が可能である。

単純パスの列挙には DFS を用いるのが良いだろう。訪問済みの頂点までのパスの総 XOR を持ちながら再帰していくとラク。

注意点としては、ラベルの最大値が $2^{60}$ であること。仮の答えの初期値を $10^{18}$ とかにしておくとバグってしまう。

実装例

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

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

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

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

using ull = unsigned long long;
constexpr ull MAX = ULLONG_MAX;

struct Edge
{
    int to;
    ull cost;
};

int main()
{
    int N, M;
    cin >> N >> M;
    Graph<Edge> G(N);
    rep(i, 0, M)
    {
        int u, v;
        ull w;
        cin >> u >> v >> w;
        u--, v--;
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }

    vector<bool> visited(N, false);
    ull ans = MAX;

    visited[0] = true;

    auto dfs = [&](auto self, int now, ull cost) -> void
    {
        if (now == N - 1)
        {
            chmin(ans, cost);
            return;
        }

        for (auto &&next : G[now])
        {
            if (visited[next.to])
                continue;

            visited[next.to] = true;
            self(self, next.to, cost ^ next.cost);
            visited[next.to] = false;
        }
    };

    dfs(dfs, 0, 0);

    cout << ans << endl;

    return 0;
}