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

I want to divide a graph with N weighted-vertices and N-1 edges into three parts such that the maximum of the sum of weights of all the vertices in each of the parts is minimized. This is the actual problem i am trying to solve, 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）的时间。

The above algorithm takes O(n^3) time, as the number of edges will be n-1 the outer loop will run (n-1)! times that takes O(n^2) the dfs will visit each vertex only one so that is O(n) time.

但问题是，n可以是＆LT; = 3000和为O（n ^ 3），时间也不好这个问题。有没有将计算解决链接的问题大于n ^ 3？

But the problem is that n can be <= 3000 and O(n^3) time is not good for this problem. Is there any other method which will calculate the solve the question in the link faster than n^3?

编辑：

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

I implemented @BorisStrandjev's algorithm in c, it gave me a correct answer for the test input in the question, but for all other test inputs it gives a wrong answer, here is a link to my code in ideone http://ideone.com/67GSa2, the output here should be 390 but the program prints 395.

我试图找到，如果我在code没有犯错，但我没有看到任何。任何人都可以请帮我在这里的答案我的code给了非常接近正确答案，所以有什么更多的算法？

I am trying to find if i have made any mistake in my code but i dont see any. Can anyone please help me here the answers my code gave are very close to the correct answer so is there anything more to the algorithm?

编辑2：

在下面的图表 -

EDIT 2:

In the following graph-

@BorisStrandjev，你的算法会选择我作为1，J为2之一迭代，但随后的第三部分（3,4）是无效的。

@BorisStrandjev, your algorithm will chose i as 1, j as 2 in one of the iterations, but then the third part (3,4) is invalid.

我终于得到，而不是V中的错误，在我的code，[我]存储我总结及其所有后代它保存v [电流]和它的祖先，否则会解决上面的例子正确的，感谢所有你的帮助。

I finally got the mistake in my code, instead of V[i] storing sum of i and all its descendants it stored V[i] and its ancestors, otherwise it would solve the above example correctly, thanks to all of you for your help.

推荐答案

是有更快的方法。

我需要一些辅助矩阵，我会离开自己创建和初始化以正确的方式给你。

I will need few auxiliary matrices and I will leave their creation and initialization in correct way to you.

第一树 - 也就是使执导的图。计算阵列 VAL [I] 为每个顶点 - 乘客一个顶点及其所有后代的数量（记住我们种的，所以现在这是有道理的）。也算布尔矩阵递减[I] [J] 将真，如果顶点我为后代顶点Ĵ。然后执行以下操作：

First of all plant the tree - that is make the graph directed. Calculate array VAL[i] for each vertex - the amount of passengers for a vertex and all its descendants (remember we planted, so now this makes sense). Also calculate the boolean matrix desc[i][j] that will be true if vertex i is descendant of vertex j. Then do the following:

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）你只需要弄清楚如何计算递减[I] [J] 和 VAL [I] 在这样的复杂性，但也不是那么复杂的任务，我想你自己看着办吧你自己。

After the execution of this cycle the answer will be in best_val. the algorithm is clearly O(n^2) you just need to figure out how to calculate desc[i][j] and VAL[i] in such complexity, but it is not so complex a task, I think you can figure it out yourself.

修改在这里，我将包括$ C $下的伪$ ​​C $ C的整个问题。我故意没有包含code之前的OP试图和他自己解决了这个问题：

EDIT Here I will include the code for the whole problem in pseudocode. I deliberately did not include the code before the OP tried and solved it by himself:

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

和最好的分裂将是 {i的后代} \ {歼后裔} ， {歼后裔} \ {i的后裔} 和的I {所有节点} \ {后裔} U {歼后裔} 。

And the best split will be {descendants of i} \ {descendants of j}, {descendants of j} \ {descendants of i} and {all nodes} \ {descendants of i} U {descendants of j}.