题目详情题解（0）讨论（0）提交记录（0）

AT_abc338_f.[ABC338F] Negative Traveling Salesman

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一个包含 NN 个顶点和 MM 条边的带权有向简单图。顶点编号为 11 到 NN，第 ii 条边是从顶点 UiU_i 指向顶点 ViV_i，权值为 WiW_i。这里，权值可以为负数，但图中不存在负权回路。

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

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

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

输入格式

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

NN MM
U1U_1 V1V_1 W1W_1
U2U_2 V2V_2 W2W_2
⋮\vdots
UMU_M VMV_M WMW_M

输出格式

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

输入输出样例

  • 输入#1

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

    输出#1

    -2

  • 输入#2

    3 2
1 2 0
2 1 0

    输出#2

    No

  • 输入#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≤N≤202 \leq N \leq 20
  • 1≤M≤N(N−1)1 \leq M \leq N(N-1)
  • 1≤Ui,Vi≤N1 \leq U_i, V_i \leq N
  • Ui≠ViU_i \neq V_i
  • (Ui,Vi)≠(Uj,Vj) (i≠j)(U_i, V_i) \neq (U_j, V_j)\ (i \neq j)
  • −106≤Wi≤106-10^6 \leq W_i \leq 10^6
  • 给定的图中不存在负权回路
  • 所有输入均为整数

样例解释 1

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

样例解释 2

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

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页