Difference between revisions of "TADM2E 6.9"

From Algorithm Wiki
Jump to: navigation, search
(Add hint)
(Undo revision 878 | Why are u doing this? What's the point? It's wiki for learning book)
 
(2 intermediate revisions by 2 users not shown)
Line 8: Line 8:
 
=== Part B ===
 
=== Part B ===
 
The easiest is just to run a preprocessing pass before running Kruskal's algorithm.  Add all edges with negative weight, and all nodes connected to those edges.  Then run Kruskal's algorithm normally until it is finished.
 
The easiest is just to run a preprocessing pass before running Kruskal's algorithm.  Add all edges with negative weight, and all nodes connected to those edges.  Then run Kruskal's algorithm normally until it is finished.
 +
 +
----
 +
=== Part B alternative solution ===
 +
<pre>
 +
DFS on a graph to determine whether it contains edges with a negative weight, maintaining pointer MIN_E to one edge with the lowest non-negative weight
 +
I. If there are no edges with a negative weight, then return MIN_E
 +
- If all edges have a non-negative weight, then the minimum weight subset is the subset of 1 edge with the lowest weight
 +
- A subgraph of 1 edge is connected
 +
 +
II. If there are edges with a negative weight, then apply the Kruskal's algorithm
 +
- Sort edges by their weight
 +
- For each connectivity component, the total weight is stored in its representative, representative's weight updates in disjoint_set's union function, initial weight = 0
 +
- Maintaining pointer MIN on the component with the lowest weight
 +
- Loop over all edges
 +
- - If edge's weight is negative, union components, if united component's weight is less than MIN, update MIN, continue
 +
- - If edge's weight is positive and at least one of the components for union has a non-negative weight, continue
 +
- - - Union with positive component via a positive edge can only increase weight, so the edge is skipped
 +
- - If edge's weight is positive, weights of both components for union are negative, and (edges weight + weight of each component is negative), union components
 +
- - - At this step, the algorithm does union 2 components with a negative weight via positive edge
 +
- - - The weight of the combined component is less than the weight of each component separately, even though an edge with a positive weight was used
 +
- - - If the weight of the combined component is less than MIN, update MIN
 +
- return MIN
 +
</pre>
 +
--[[User:Bkarpov96|Bkarpov96]] ([[User talk:Bkarpov96|talk]]) 14:47, 22 July 2020 (UTC)

Latest revision as of 08:13, 23 July 2020

Hints

Look very carefully at the definition of T, versus the definition of an MST.


Part A

The problem explicitly states that T is a "minimum weight connected subset", not "minimum weight connected subset with exactly N-1 edges", so it doesn't have to be an MST. If all weights are positive or zero, then T happens to be the same as the MST, but if negative weights are allowed, all negative weight edges must be included in T to drive the total as low as possible.

Part B

The easiest is just to run a preprocessing pass before running Kruskal's algorithm. Add all edges with negative weight, and all nodes connected to those edges. Then run Kruskal's algorithm normally until it is finished.


Part B alternative solution

DFS on a graph to determine whether it contains edges with a negative weight, maintaining pointer MIN_E to one edge with the lowest non-negative weight
I. If there are no edges with a negative weight, then return MIN_E
- If all edges have a non-negative weight, then the minimum weight subset is the subset of 1 edge with the lowest weight
- A subgraph of 1 edge is connected

II. If there are edges with a negative weight, then apply the Kruskal's algorithm
- Sort edges by their weight
- For each connectivity component, the total weight is stored in its representative, representative's weight updates in disjoint_set's union function, initial weight = 0
- Maintaining pointer MIN on the component with the lowest weight
- Loop over all edges
- - If edge's weight is negative, union components, if united component's weight is less than MIN, update MIN, continue
- - If edge's weight is positive and at least one of the components for union has a non-negative weight, continue
- - - Union with positive component via a positive edge can only increase weight, so the edge is skipped
- - If edge's weight is positive, weights of both components for union are negative, and (edges weight + weight of each component is negative), union components
- - - At this step, the algorithm does union 2 components with a negative weight via positive edge
- - - The weight of the combined component is less than the weight of each component separately, even though an edge with a positive weight was used
- - - If the weight of the combined component is less than MIN, update MIN
- return MIN

--Bkarpov96 (talk) 14:47, 22 July 2020 (UTC)