c - 将图分成三部分，使三部分权重之和的最大值最小化

Question

我想将一个有 N 个加权顶点和 N-1 条边的图分成三个部分，使每个部分中所有顶点的权重总和的最大值最小化。这是我要解决的实际问题，http://www.iarcs.org.in/inoi/contests/jan2006/Advanced-1.php

我考虑过下面的方法

/*Edges are stored in an array E, and also in an adjacency matrix for depth first search.
Every edge in E has two attributes a and b which are the nodes of the edge*/
min-max = infinity
for i -> 0 to length(E):
   for j -> i+1 to length(E):
     /*Call depth first search on the nodes of both the edges E[i] and E[j]
     the depth first search returns the sum of weights of the vertices it visits,
     we keep track of the maximum weight returned by dfs*/
     Adjacency-matrix[E[i].a][E[i].b] = 0;
     Adjacency-matrix[E[j].a][E[j].b] = 0;
     max = 0
     temp = dfs(E[i].a) 
     if temp > max then max = temp
     temp = dfs(E[i].b) 
     if temp > max then max = temp
     temp = dfs(E[i].a) 
     if temp > max then max = temp
     temp = dfs(E[i].a) 
     if temp > max then max = temp

     if max < min-max
        min-max = max
     Adjacency-matrix[E[i].a][E[i].b] = 1;
     Adjacency-matrix[E[j].a][E[j].b] = 1;
    /*The depth first search is called four times but it will terminate one time
   if we keep track of the visited vertices because there are only three components*/

  /*After the outer loop terminates what we have in min-max will be the answer*/

上述算法需要 O(n^3) 时间，因为边数将为 n-1，外层循环将运行 (n-1)!花费 O(n^2) 的时间，dfs 将只访问每个顶点一次，所以这是 O(n) 时间。

但问题是 n 可以 <= 3000 并且 O(n^3) 时间不适合这个问题。有没有其他方法可以比 n^3 更快地计算解决链接中的问题？

编辑:

我在 c 中实现了@BorisStrandjev 的算法，它为问题中的测试输入提供了正确答案，但对于所有其他测试输入，它给出了错误答案，这是我在 ideone 中的代码的链接 http://ideone.com/67GSa2 ，这里的输出应该是 390 但程序打印 395。

我试图找出我的代码中是否有任何错误，但我没有看到任何错误。任何人都可以在这里帮助我我的代码给出的答案非常接近正确答案那么算法还有什么吗？

编辑 2:

在下图中-

@BorisStrandjev，您的算法将在其中一次迭代中选择 i 作为 1，j 作为 2，但是第三部分 (3,4) 无效。

编辑 3

我终于在我的代码中犯了错误，而不是 V[i] 存储 i 及其所有后代的总和，而是存储 V[i] 及其祖先，否则它会正确解决上面的例子，感谢大家您的帮助。

Answer 1

是的，有更快的方法。

我将需要一些辅助矩阵，我会把它们的创建和初始化的正确方法留给你。

首先种树 - 即使图形有向。为每个顶点计算数组 VAL[i] - 一个顶点及其所有后代的乘客数量(记住我们种植了，所以现在这很有意义)。还计算 bool 矩阵 desc[i][j] 如果顶点 i 是顶点 j 的后代，则该矩阵为真。然后执行以下操作:

best_val = n
for i in 1...n
  for j in i + 1...n
    val_of_split = 0
    val_of_split_i = VAL[i]
    val_of_split_j = VAL[j]
    if desc[i][j] val_of_split_j -= VAL[i] // subtract all the nodes that go to i
    if desc[j][i] val_of_split_i -= VAL[j]
    val_of_split = max(val_of_split, val_of_split_i)
    val_of_split = max(val_of_split, val_of_split_j)
    val_of_split = max(val_of_split, n - val_of_split_i - val_of_split_j)
    best_val  = min(best_val, val_of_split)

执行此循环后，答案将在 best_val 中。该算法显然是 O(n^2) 您只需要弄清楚如何计算 desc[i][j] 和 VAL[i] 这么复杂，但它不是那么复杂的任务，我想你可以自己弄清楚。

编辑 在这里，我将在伪代码中包含整个问题的代码。在 OP 尝试并自行解决之前，我故意不包含代码:

int p[n] := // initialized from the input - price of the node itself
adjacency_list neighbors := // initialized to store the graph adjacency list

int VAL[n] := { 0 } // the price of a node and all its descendants
bool desc[n][n] := { false } // desc[i][j] - whether i is descendant of j

boolean visited[n][n] := {false} // whether the dfs visited the node already
stack parents := {empty-stack}; // the stack of nodes visited during dfs

dfs ( currentVertex ) {
   VAL[currentVertex] = p[currentVertex]
   parents.push(currentVertex)
   visited[currentVertex] = true
   for vertex : parents // a bit extended stack definition supporting iteration
       desc[currentVertex][vertex] = true
   for vertex : adjacency_list[currentVertex]
       if visited[vertex] continue
       dfs (currentvertex)
       VAL[currentVertex] += VAL[vertex]
   perents.pop

calculate_best ( )
    dfs(0)
    best_val = n
    for i in 0...(n - 1)
      for j in i + 1...(n - 1)
        val_of_split = 0
        val_of_split_i = VAL[i]
        val_of_split_j = VAL[j]
        if desc[i][j] val_of_split_j -= VAL[i]
        if desc[j][i] val_of_split_i -= VAL[j]
        val_of_split = max(val_of_split, val_of_split_i)
        val_of_split = max(val_of_split, val_of_split_j)
        val_of_split = max(val_of_split, n - val_of_split_i - val_of_split_j)
        best_val  = min(best_val, val_of_split)
    return best_val

最好的分割是{descendants of i}\{descendants of j}, {descendants of j}\{descendants of i} and {所有节点}\{i 的后代} U {j 的后代}。