AT_abc338_f [ABC338F] Negative Traveling Salesman

题目描述

有一个包含 $N$ 个顶点和 $M$ 条边的带权有向简单图。顶点编号为 $1$ 到 $N$，第 $i$ 条边是从顶点 $U_i$ 指向顶点 $V_i$，权值为 $W_i$。这里，权值可以为负数，但图中不存在负权回路。

请判断是否存在一条经过所有顶点至少一次的“行走”（Walk），如果存在，求经过的边权之和的最小值。注意，如果同一条边经过多次，其权值会被多次累加。

所谓“经过所有顶点至少一次的行走”是指，存在一个顶点序列 $v_1,v_2,\dots,v_k$，满足以下条件：

• 对于所有 $i\ (1\leq i\leq k-1)$，存在一条从 $v_i$ 到 $v_{i+1}$ 的有向边；
• 对于所有 $j\ (1\leq j\leq N)$，存在至少一个 $i\ (1\leq i\leq k)$ 使得 $v_i = j$。

输入格式

输入以如下格式从标准输入读入。

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

输出格式

如果存在经过所有顶点至少一次的行走，输出经过的边权之和的最小值；否则输出 No。

输入输出样例 #1

输入 #1

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

输出 #1

-2

输入输出样例 #2

输入 #2

3 2
1 2 0
2 1 0

输出 #2

No

输入输出样例 #3

输入 #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

输出 #3

-449429

说明/提示

限制条件

• $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)\ (i \neq j)$
• $-10^6 \leq W_i \leq 10^6$
• 给定的图中不存在负权回路
• 所有输入均为整数

样例解释 1

按顶点 $2\rightarrow 1\rightarrow 2\rightarrow 3$ 的顺序行走，可以经过所有顶点一次以上，经过的边权之和为 $(-3)+5+(-4)=-2$，这是最小值。

样例解释 2

不存在经过所有顶点至少一次的行走。

由 ChatGPT 4.1 翻译