将图分成三个部分，使得这三个部分的权重和的最大值最小化
我想将一个具有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
我终于在我的代码中得到了错误，而不是Vi存储i和它的所有后代的和，它存储了Vi和它的祖先，否则它将正确地解决上面的例子，感谢大家的帮助。
回答 3
Stack Overflow用户
发布于 2013-01-07 19:42:05
是的，有更快的方法。
我将需要一些辅助矩阵，我将以正确的方式将它们的创建和初始化留给您。
首先，种下树--也就是让图形有方向。计算每个顶点的数组VAL[i] -一个顶点及其所有子节点的乘客数量(记住我们种植的，所以现在这是有意义的)。还要计算布尔矩阵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]，但这并不是一项复杂的任务，我认为你可以自己解决。
编辑在这里我将把整个问题的代码包含在伪代码中。在操作员尝试自己解决它之前，我故意不包括代码：
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}和{all nodes} \ {descendants of i} U {descendants of j}。
Stack Overflow用户
发布于 2013-01-07 19:35:27
EDIT 4:这将不起作用！
如果你以3,4,5, 6，1,2的顺序处理the link中的节点，在处理6之后，(我认为)你会得到以下集合：{{3,4}，{5}，{6}}，{{3,4,5}，{6}}，{{3,4,5,6}}，没有简单的方法可以再次拆分它们。
我只是在这里留下这个答案，以防其他人正在考虑DP算法。
在DP算法中查看所有已经处理过的邻居可能是可行的。
。
我在考虑Dynamic Programming算法，其中矩阵是(项目x集合的数量)
n = number of sets
k = number of vertices
// row 0 represents 0 elements included
A[0, 0] = 0
for (s = 1:n)
A[0, s] = INFINITY
for (i = 1:k)
for (s = 0:n)
B = A[i-1, s] with i inserted into minimum one of its neighbouring sets
A[i, s] = min(A[i-1, s-1], B)) // A[i-1, s-1] = INFINITY if s-1 < 0EDIT: DP的说明：
这是一个相当基本的Dynamic Programming算法。如果你需要更好的解释，你应该多读一些，它是一个非常强大的工具。
A是一个矩阵。行i表示包含到i为止的所有顶点的图。列c表示集合数量=c的解。
因此，A[2,3]会给出包含项目0、项目1和项目2和3集合的图的最佳结果，因此每个集合都在自己的集合中。
然后从项目0开始，计算每个集合数量的行(唯一有效的是集合数量= 1)，然后使用上面的公式计算项目1，然后是项目2，依此类推。
然后，A[a, b]是最优解决方案，所有顶点都包含a个集合和b个集合。因此，您只需返回A[k, n] (包含所有顶点和目标集合数量的集合)。
EDIT 2: Complexity
O(k*n*b)，其中b是节点的分支因子(假设您使用adjacency list)。
因为是n = 3，所以这是O(3*k*b) = O(k*b)。
EDIT 3:决定顶点应该添加到的相邻集合
在union find结构中保留n个数组，每个数组包含k个元素，每个集合指向该集合的总和。对于每个新行，为了确定顶点可以添加到哪些集合，我们使用其adjacency list并查找其每个邻居的集合和值。一旦我们找到了最佳选项，我们就可以将该元素添加到适用的集合中，并通过添加的元素的值来递增其和。
你会注意到算法只向下看1行，所以我们只需要跟踪最后一行(而不是存储整个矩阵)，并且可以修改前一行的n个数组，而不是复制它们。
Stack Overflow用户
发布于 2013-01-07 19:45:36
您可以使用二进制搜索和DFS的组合来解决此问题。
下面是我将如何继续：
- 计算图形的总权重，并找到图形中最重的边。现在我们必须在这个范围内运行一个二进制搜索: Sum，Sum.
- In maxEdge
- ，=( MaxEdge +
/ 2)。现在，选择一个开始节点并执行DFS s.t。在子图中遍历的边的总和尽可能地接近“中间”。但是保持这个和小于中间值。这将是一个子图。在相同的迭代中，现在选择另一个未被前一个DFS标记的节点。以同样的方式执行另一个DFS。同样，再做一次，因为我们需要将图形分成3部分。
- 最小值。上面计算的3个子图中的权重是这次迭代的解决方案。
- 继续运行这个二进制搜索，直到它的结束变量超过了它的开始变量。
在步骤4中获得的所有min的最大就是您的答案。为了得到3-sub图，你可以做额外的记账。
对数阶数复杂度:N()，其中Sum是图的总权重。
我刚刚注意到你谈到了加权顶点，而不是边。在这种情况下，只需将边视为我的解决方案中的顶点。它应该还能工作。
https://stackoverflow.com/questions/14194519
复制相似问题
腾讯云开发者
