0

给定：未加权无向图（循环）G(V,E)，每个顶点都有两个给定的值（比如 A 和 B），并且没有两个相邻顶点具有相同的 A 值。
找到具有最大 B 值总和的简单路径，具有以下约束：
1）该路径包含相同 A 值的顶点，或者它最多可以有两个不同的 A 值（这些值必须是交替的，因为没有两个相邻的顶点可以具有相同的 A 值）

图

在图中。最长的简单路径从顶点 2 开始，到 5 结束，所有顶点最多有 2 个不同的值 1 和 2，它们在路径中以交替方式 1、2、1、2、1 输出并输出 B 值总和。
请记住：如果 B 的值 6 为 13，则顶点 6 可能是答案，因为解决方案路径的总和仅为 12。

int dfs(int source, int parent, int score){
        for each vertex V(V!=p) connected to source:
           if(!vis[V]{
               if(A[parent]==A[V]){ 
                    recur : dfs(V,source,B[source]+score)
                 }
            }

  return score+B[source];
}

它给出了错误的答案。不。顶点数 <=1000000

4

0 回答 0