无向图仅允许边单次通行的节点值求和最重路径求解问题

这个问题可以通过边双连通分量缩点的方法高效求解，核心逻辑是利用桥和边双连通分量的特性拆分问题，把复杂图问题转化为简单的树路径问题：

步骤1：拆分边双连通分量 #

首先对原图做边双连通分量（E-BCC）分解：

• 边双连通分量指的是内部不存在桥（割边）的极大子图，分量内任意两点之间至少存在两条边不相交的路径，因此分量内的非桥边可以任意多次通行，你进入分量后总能找到路径回到出口，不需要担心无法离开的问题。
• 原图中所有的桥都是连接不同边双连通分量的边，这部分边按约束只能走一次。

步骤2：缩点建图 #

把每个边双连通分量缩成一个单独的节点，所有桥作为缩点后节点之间的连接边，此时得到的新图一定是树结构（不存在环，否则说明还有未拆分的边双连通分量）。

步骤3：计算每个缩点的权重 #

针对每个边双连通分量，计算该分量内可以获得的最大节点权重和：

• 若允许进入分量后再离开：只要分量内节点权重为正，你完全可以遍历分量内所有正权重的节点后再离开，因此权重就是分量内所有正权重节点的总和。
• 若分量是路径的终点不需要离开：权重规则和上面一致，因为你不需要留出口，能拿到的最大和仍然是所有正权重节点的总和（如果全为负则只取分量内单个最大权重的节点）。

步骤4：求解树的最大路径和 #

现在问题转化为经典的树的最大路径和问题：在缩点得到的树上找一条边不重复的简单路径（对应桥只走一次），使得路径上所有缩点的权重总和最大，该问题可以用深度优先搜索在O(n)时间复杂度内求解，n是缩点后的节点数量。

你提到的边染色思路是可行的，适合小规模图的求解：

• 给原图中每座桥分配唯一的颜色标记，非桥边不需要做特殊标记（或统一标记为可重复使用的颜色）。
• 搜索路径时，仅记录已经使用过的桥的颜色，约束同色的桥只能走一次，非桥边无使用次数限制。
• 这种方案本质是带状态的深度优先搜索/广度优先搜索，好处是实现简单，不需要做复杂的图论拆分，缺点是如果图的桥数量很多，状态空间会爆炸，仅适合节点规模小于20的小图使用。

内容的提问来源于stack exchange，提问作者Charlie Lomello