Question

帮忙翻译一下,一段计算机专业英语

We propose a data structure to maintain a collection of vertex-disjoint trees under a sequence of two kinds of operations: a link operation that combines two trees into one by adding an edge, and a cut operation that divides one tree into two by deleting an edge. Our data structure requires O(log n) time per operation when the time is amortized over a sequence of operations. Using our data structure, we obtain new fast algorithms for the following problems: (1) Computing deepest common ancestors. (2) Solving various network flow problems including finding maximum flows, blocking flows, and acyclic flows. (3) Computing certain kinds of constrained minimum spanning trees. (4) Implementing the network simplex algorithm for the transshipment problem. Our most significant application is (2); we obtain an O(mn log n)-time algorithm to find a maximum flow in a network of n vertices and m edges, beating by a factor of log n the fastest algorithm previously known for sparse graphs.
翻译软件翻出来的就不要了

Answer 1

我们提出一个数据结构以维持收藏顶点相交的树木下一个序列的两种业务: 连结运作相结合,两棵树变成了一个加一条边, 和减低运作,把树一分为二,删去了优势. 我们的数据结构要求为O(logn)时间,每次行动时摊销顺序作业. 用我们的数据结构中,我们获得了新的快速算法了以下问题:(1)电脑最深的共同祖先. (2)解决各种网络流问题包括找到最大流量,阻塞流动,以及循环流动. (3)计算某种约束小树. (四)实施网络单纯形算法的转运问题. 我们最重要的应用是(2); 我们得到一个O(mnlogn)时间算法来找到一个网络最大流的N顶点和m 边,跳动的系数logn最快的算法,原名为sparsegraphs

Answer 2

建议你用金山快译

Answer 3

我们计画一笔数据构成维持顶点的一个收集- 脱节树在二类型 操作的序列之下: 结合二棵树变成一的联编操作藉由增加边缘 , 和把一棵树分为的缩减操作二藉由划除边缘。 当时间过度被分期偿还操作的序列时候 , 我们的数据构成需要 O(圆木 n) 每操作时间。 使用我们的数据构成 , 我们获得新的快速运算法则作为下列各项问题: (1)计算机最深的通常祖先。 (2)解决发现最大的流程包括的各种不同的网络流问题,阻断流动, 和非循环式的流程。 (3)计算某类型 强迫的最小量跨越树。 (4)为转载他船或列车问题实现网络单纯的运算法则。 我们的最重要的申请是 (2) ；我们获得 O(mn 圆木 n)- 时间运算法则在 n vertices 和 m 边缘的一个网络中找最大的流程, 藉着圆木 n 最快速的运算法则的一个因素打先前以稀疏的曲线图闻名。

Answer 4

我们对维持一个顶点的收集计画数据结构-脱节树在操作的二个类型的序列之下: 联编操作哪一联合二树进入一之内藉由增加一边缘, 和一削减操作哪一分歧一树进入二之内藉由划除一边缘。 我们的数据结构需要 O(记录 n) 时间每一操作当那时间是分期偿还在操作的序列之上。 使用我们的数据结构，我们获得新的斋戒运算法则为下列的问题: (1) 计算机深的通常祖先。 (2) 解决各种不同的网络流程问题包括发现最大值流程, 阻断流程, 和非循环式的流程。 (3) 计算机特定类型的强迫最小量跨越树。 (4) 为转载他船或列车问题实现网络单纯的运算法则。 我们最重要的申请是;(2) 我们获得 O(mn 记录 n)-时间运算法则找最大值流程在一个 n 顶点的网络中和 m 边缘, 打由因素记录 n 那快速的先前被以稀疏的曲线图闻名的运算法则。