@[ChrysanthBlossom](/user/555065) 这样极有可能无解（不同车不能走同一条边）
by _Weslie_ @ 2023-08-13 14:09:57
@[喜羊羊本羊](/user/511959) 这里的无解指的是只能暴力吗
by AfterFullStop @ 2023-08-13 19:00:35
@[ChrysanthBlossom](/user/555065) 不是，是根本没有解。
这样如果出现一条边不被经过两次就无解的情况就会无解。
假设有唯一解环路如下图。
红色为一辆车，蓝色为一辆车。
这样一定要经过重复边，无解。
by _Weslie_ @ 2023-08-13 20:58:51
@[喜羊羊本羊](/user/511959) 您似乎有点误解我的意思了
我的意思是把题目变成这样：
>给定一个 $n$ 个点 $m$ 条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。
>
>不允许多次经过一条边或者一个点。
这个“两辆车”是从何而来的？题目中不是只让求一条路径吗
by AfterFullStop @ 2023-08-13 21:02:46
@[ChrysanthBlossom](/user/555065) 那有解，但是我不会写（
和原版思路不会有太大变化
by _Weslie_ @ 2023-08-13 21:11:37
@[ChrysanthBlossom](/user/555065) @[喜羊羊本羊](/user/511959) 挑战哈密瓜/lh/lh，领图灵奖罢/lh/lh
by WrongAnswer_90 @ 2023-11-11 11:24:08
@[ChrysanthBlossom](/user/555065) 状压点边状态可以 $\mathcal O(2^{n+m}n^2)$ 之类的/lh/lh，想更优可能需要科技
by WrongAnswer_90 @ 2023-11-11 11:26:05
@[WrongAnswer_90](/user/134510) 这个问题能约化为哈密顿吗
by AfterFullStop @ 2023-11-11 11:32:53
@[ChrysanthBlossom](/user/555065) 这不就是哈密顿路吗/wul
by WrongAnswer_90 @ 2023-11-11 11:42:16
@[WrongAnswer_90](/user/134510) 好像确实是，哈密顿路能约化为这题
by AfterFullStop @ 2023-11-11 11:52:07