F - Negative Traveling Salesman Editorial by yuto1115
解説頂点 \(i\) から頂点 \(j\) までの最短経路の長さを \(d_{i,j}\) とおきます。このとき、答えは \((1,2,\dots,N)\) の順列 \((p_1,p_2,\dots,p_N)\) 全てに対する \(d_{p_1,p_2}+d_{p_2,p_3}+\dots+d_{p_{N-1},p_N}\) の最小値と一致します。
\(p_1\) から \(p_2\) までの最短経路、\(p_2\) から \(p_3\) までの最短経路、\(\dots\)、\(p_{N-1}\) から \(p_N\) までの最短経路をこの順に繋げてできるウォークが条件を満たすのは明らかなので、逆に、条件を満たすもののうち通る辺の重みの総和が最小になるようなウォーク（以下単に最適解と呼ぶ）であって上述の形で表されるものが必ず存在することを示せばよい。
最適解をウォーク \(x_1\rightarrow x_2\rightarrow \dots \rightarrow x_k\) とおく。ここで、\(x_1\neq x_k\) を仮定してよい（\(x_1=x_k\) であるとき経路全体が \(1\) つの閉路になるが、負閉路でないことから重みが非負の辺を \(1\) つ選ぶことができるので、その辺を削除して閉路を”切り開く”ことで、通る頂点の集合を不変に保ったまま、通る辺の重みの総和を増加させることなく閉路でないウォークを得られる）。よって、\(x_1,x_2,\dots,x_k\) の中から、\(x_1\) と \(x_k\) を含む \(N\) 頂点を重複なく（すなわち、\(1,2,\dots,N\) が一度ずつ現れるように）選ぶことができる。ここで選ばなかった部分については、選んだ頂点のうち最も近い \(2\) 頂点の最短経路で繋ぐのが明らかに最適であるから、このウォークは上述の形で表されている。
証明
以下の動的計画法を考えます。
- \(\mathrm{dp}[S][i]\): 任意の頂点から始まって頂点 \(i\) で終わるようなウォークのうち、通る頂点の集合が \(S\) であるようなものに対する通る辺の重みの総和の最小値
遷移としては、まだ訪れていない頂点のうち次に訪れる頂点 \(j\) を全探索して、\(\mathrm{dp}[S\cup \{j\}][j]\leftarrow \min\{\mathrm{dp}[S\cup \{j\}][j],\mathrm{dp}[S][i]+d_{i,j}\}\) とすればよいです。
よって、Floyd-Warshall 法などを用いて全ての \(i,j\) に対する \(d_{i,j}\) を前計算しておくことで、全体として \(O(N^3+2^NN^2)\) などの計算量で解くことができます。
実装例 (C++) :
#include<bits/stdc++.h>
using namespace std;
const int inf = 1 << 30;
void chmin(int &a, int b) { a = min(a, b); }
int main() {
int n, m;
cin >> n >> m;
vector d(n, vector<int>(n, inf));
for (int i = 0; i < n; i++) d[i][i] = 0;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
--u, --v;
d[u][v] = w;
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (d[i][k] == inf or d[k][j] == inf) continue;
chmin(d[i][j], d[i][k] + d[k][j]);
}
}
}
vector dp(1 << n, vector<int>(n, inf));
for (int i = 0; i < n; i++) dp[1 << i][i] = 0;
for (int bit = 1; bit < (1 << n) - 1; bit++) {
for (int i = 0; i < n; i++) {
if (~bit >> i & 1) continue;
if (dp[bit][i] == inf) continue;
for (int j = 0; j < n; j++) {
if (bit >> j & 1) continue;
if (d[i][j] == inf) continue;
chmin(dp[bit | 1 << j][j], dp[bit][i] + d[i][j]);
}
}
}
int ans = inf;
for (int i = 0; i < n; i++) {
chmin(ans, dp[(1 << n) - 1][i]);
}
if (ans == inf) cout << "No" << endl;
else cout << ans << endl;
}
posted:
last update: