問題

町が $N$ 個あり、 $M$ 本の双方向に移動可能な道で結ばれています。町には $1$ から $N$ までの番号が、道には $1$ から $M$ までの番号が付いています。 $i(1 \le i \le M)$ 番目の道は、町 $A_i$ と町 $B_i$ の間を結んでいて、通ると $Hi$ の幸福を得ることができます。町 $s$ と町 $t$ を $s \neq t$ を満たすように選び、同じ町を二回以上訪れないように町 $s$ から町 $t$ まで移動するとき、得られる幸福の総和の最大値を求めてください。

制約

$2 \le N \le 12$
$\displaystyle 1 \le M \le \frac{N \times (N-1)}{2}$
$1 \le H_i \le 10^7$

考え方

巡回セールスマン問題に似た要領で解くことができる。つまり

$dp[i][j]$ := 訪問頂点を $i$ として、現在 $j$ にいるときの最大値

とする。その時の遷移は、頂点 $i$ は訪問済で、頂点 $j$ は未訪問であるようなときに、

訪問後の値 = 訪問前の値＋ $i$ から $j$ への辺の値

となるので、訪問後の値の最大値を集合の小さい状態から徐々に求めていけば良い。

       public void solve(int testNumber, MyInput in, PrintWriter out) {

            int n = in.nextInt(), m = in.nextInt();

            int[][] mat = new int[n][n];
            fill(mat, -1);
            for (int i = 0; i < m; i++) {
                int a = in.nextInt()-1, b = in.nextInt()-1, c = in.nextInt();
                mat[a][b] = c;
                mat[b][a] = c;
            }

            long[][] dp = new long[1 << n][n];
            for (int bit = 0; bit < 1 << n; bit++) {
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < n; j++) {
                        if ((bit >> i & 1) == 1 && (bit >> j & 1) == 0 && mat[i][j] != -1) {
                            dp[bit | 1 << j][j] = max(dp[bit | 1 << j][j], dp[bit][i] + mat[i][j]);
                        }
                    }
                }
            }

            long ans = 0;
            for (int i = 0; i < 1 << n; i++) {
                for (int j = 0; j < n; j++) {
                    ans = max(ans, dp[i][j]);
                }
            }

            out.println(ans);
        }