F - Negative Traveling Salesman

Problem Statement

There is a weighted simple directed graph with $N$ vertices and $M$ edges. The vertices are numbered $1$ to $N$, and the $i$-th edge has a weight of $W_i$ and extends from vertex $U_i$ to vertex $V_i$. The weights can be negative, but the graph does not contain negative cycles.

Determine whether there is a walk that visits each vertex at least once. If such a walk exists, find the minimum total weight of the edges traversed. If the same edge is traversed multiple times, the weight of that edge is added for each traversal.

Here, "a walk that visits each vertex at least once" is a sequence of vertices $v_1,v_2,\dots,v_k$ that satisfies both of the following conditions:

• For every $i$ $(1\leq i\leq k-1)$, there is an edge extending from vertex $v_i$ to vertex $v_{i+1}$.
• For every $j\ (1\leq j\leq N)$, there is $i$ $(1\leq i\leq k)$ such that $v_i=j$.

Constraints

• $2\leq N \leq 20$
• $1\leq M \leq N(N-1)$
• $1\leq U_i,V_i \leq N$
• $U_i \neq V_i$
• $(U_i,V_i) \neq (U_j,V_j)$ for $i\neq j$
• $-10^6\leq W_i \leq 10^6$
• The given graph does not contain negative cycles.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$
$U_1$ $V_1$ $W_1$
$U_2$ $V_2$ $W_2$
$\vdots$
$U_M$ $V_M$ $W_M$

Output

If there is a walk that visits each vertex at least once, print the minimum total weight of the edges traversed. Otherwise, print No.

Sample Input 1

3 4
1 2 5
2 1 -3
2 3 -4
3 1 100

Sample Output 1

-2

By following the vertices in the order $2\rightarrow 1\rightarrow 2\rightarrow 3$, you can visit all vertices at least once, and the total weight of the edges traversed is $(-3)+5+(-4)=-2$. This is the minimum.

Sample Input 2

3 2
1 2 0
2 1 0

Sample Output 2

No

There is no walk that visits all vertices at least once.

Sample Input 3

5 9
1 2 -246288
4 5 -222742
3 1 246288
3 4 947824
5 2 -178721
4 3 -947824
5 4 756570
2 5 707902
5 1 36781

Sample Output 3

-449429

解题思路

  之前在洛谷上做过类似的题目：P8733 [蓝桥杯 2020 国 C] 补给，所以比赛的时候一下就做出来了。

  看到数据范围容易想到状压 dp，定义 $f(i,j)$ 表示从起点走到当前点 $j$ 且经过的节点所表示的二进制集合为 $i$ 的所有路径中权值的最小值，状态转移方程为 $f(i,j) = \min\limits_{k \in i} \left\{ {f(i \setminus \{k\}, k) + g(k,j)} \right\}$。其中 $g(k,j)$ 指 $k \to j$ 的最短距离，任意两点间的最短路可以通过 Floyd 算法求得。另外 $k \to j$ 所经过的中间节点（不含 $k$ 和 $j$）不会被加入到集合中，这里每次只会加入最后到达的节点。

  为什么这样做是正确的呢？首先上面的做法本质是找到一个 $0 \sim n-1$ 的排列 $p$，使得 $\sum\limits_{i=1}^{n-1}{g(i-1,i)}$ 最小，这条路径必然会经过每个节点至少一次。而最优解所对应的路径中，节点 $0 \sim n-1$ 也必然出现至少一次，对于每个编号的节点从中任选出一个（路径的起点和终点必选），那么整个路径就会被分成 $n-1$ 段，显然每一段的长度必然是对应两端点的最短路径，否则就可以用更短的路径来替换，与最优解矛盾了。

  最后的答案为 $\min\limits_{0 \leq i \leq n-1}\left\{f(2^{n}-1, \, i)\right\}$。

  AC 代码如下，时间复杂度为 $O(n^3 + 2^n \cdot n^2)$：

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

const int N = 25, M = 1 << 20;

int g[N][N];
int f[M][N];

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    memset(g, 0x3f, sizeof(g));
    for (int i = 1; i <= n; i++) {
        g[i][i] = 0;
    }
    while (m--) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        u--, v--;
        g[u][v] = min(g[u][v], w);
    }
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
            }
        }
    }
    memset(f, 0x3f, sizeof(f));
    for (int i = 0; i < n; i++) {
        f[1 << i][i] = 0;
    }
    for (int i = 1; i < 1 << n; i++) {
        for (int j = 0; j < n; j++) {
            if (i >> j & 1) {
                for (int k = 0; k < n; k++) {
                    if (j == k) continue;
                    if (i >> k & 1) {
                        f[i][j] = min(f[i][j], f[i ^ 1 << j][k] + g[k][j]);
                    }
                }
            }
        }
    }
    int ret = 0x3f3f3f3f;
    for (int i = 0; i < n; i++) {
        ret = min(ret, f[(1 << n) - 1][i]);
    }
    if (ret >= 0x3f3f3f3f >> 1) printf("No");
    else printf("%d", ret);
    
    return 0;
}

  ps：这题还可以建分层图然后跑 spfa，一开始用 std::array<int, 2> 来存二元组结果 TLE 了，然后改成 std::pair<int, int> 刚好卡过去，最慢的数据跑了 $5989 \text{ ms}$，挺哈人的（）

  AC 代码如下，最坏情况下的时间复杂度为 $O(2^n \cdot n^3)$：

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

typedef pair<int, int> PII;

const int N = 25, M = 1 << 20;

int g[N][N];
int dist[M][N];
bool vis[M][N];

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    memset(g, 0x3f, sizeof(g));
    while (m--) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        u--, v--;
        g[u][v] = min(g[u][v], w);
    }
    queue<PII> q;
    memset(dist, 0x3f, sizeof(dist));
    for (int i = 0; i < n; i++) {
        q.push({1 << i, i});
        dist[1 << i][i] = 0;
        vis[1 << i][i] = true;
    }
    while (!q.empty()) {
        auto p = q.front();
        q.pop();
        vis[p.first][p.second] = false;
        for (int i = 0; i < n; i++) {
            if (dist[p.first | 1 << i][i] > dist[p.first][p.second] + g[p.second][i]) {
                dist[p.first | 1 << i][i] = dist[p.first][p.second] + g[p.second][i];
                if (!vis[p.first | 1 << i][i]) {
                    vis[p.first | 1 << i][i] = true;
                    q.push({p.first | 1 << i, i});
                }
            }
        }
    }
    int ret = 0x3f3f3f3f;
    for (int i = 0; i < n; i++) {
        ret = min(ret, dist[(1 << n) - 1][i]);
    }
    if (ret >= 0x3f3f3f3f >> 1) printf("No");
    else printf("%d", ret);
    
    return 0;
}

参考资料

  Editorial - AtCoder Beginner Contest 338：https://atcoder.jp/contests/abc338/editorial/9180