Negative Traveling Salesman

题目描述

有一个带权有向简单图，包含 $N$ 个顶点和 $M$ 条边。 顶点编号为 $1$ 到 $N$，第 $i$ 条边的权重为 $W_i$，从顶点 $U_i$ 指向顶点 $V_i$。 权重可以为负，但图中不包含负权回路。 判断是否存在一条至少访问每个顶点一次的游走。如果存在，求被遍历的边权重总和的最小值。 如果同一条边被遍历多次，则每次遍历均累加该边的权重。 这里，“至少访问每个顶点一次的游走”是指顶点序列 $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$。

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

-2

3 2
1 2 0
2 1 0

No

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

-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$ 所给图不存在负权回路。 所有输入值均为整数。按顶点顺序 $2\rightarrow 1\rightarrow 2\rightarrow 3$ 进行，可以至少访问所有顶点一次，所遍历边的权重总和为 $(-3)+5+(-4)=-2$。 这是最小值。
不存在一条可访问所有顶点至少一次的游走。

标签: AtCoder|abc338F

来源

AtCoder|abc338F