Define a closure of a directed graph G=(V,E) as an induced set of vertexes of G, where the out-tended edges in E start at some vertex in the closure of G and end at some vertex in the closure, too. More formally, closure is defined as a set of vertexes V′⊆V, such that ∀u∈V′,s.t.∀⟨u,v⟩∈E,v∈V′.
For the Maximum Weight Closure of a Graph, we define it as, with starting out endowing vertexes in V′ costs called wu, the maximum value of u∈V′∑wu.
§ 2. Construction of Algorithm
Add a source s and a sink t to the original graph, endow the origin edges in E with capacities that +∞, and connect s with points with positive costs with the points' costs as capacities on them while t connects to those with negative costs with the minus points' costs as capacities on them, where +∞ is defined as any number greater or equal to ∑∣wi∣.