求解带双顶点成本与边成本的无向图最小成本算法

Hey there! Let's work through this problem together. The key insight here is to model this as a minimum cut problem in a flow network—this is a standard trick for binary choice problems with connectivity constraints, and it'll give us an efficient, minimal-cost solution.

First, Let's Clarify the Problem #

Just to make sure we're aligned:

• We have an undirected graph where every edge has a cost.
• Each vertex has two choices: pay cost1 to be type 1, or cost2 to be type 2.
• An edge only counts towards graph connectivity if its two endpoints are different types.
• We need to pick a type for every vertex such that the entire graph is connected via these cross-type edges, and our total cost (sum of vertex choice costs + sum of cross-type edge costs) is as small as possible.

Step 1: Build the Auxiliary Flow Graph #

We'll construct a new directed graph to model our choices and constraints:

1. Add a source and sink: Create a source node S (representing type 1) and a sink node T (representing type 2).
2. Connect vertices to source/sink:
   • For each original vertex v, add an edge from S to v with capacity equal to cost2[v]. This represents the cost we'd pay if we don't choose type 2 for v (i.e., if v ends up in the S partition/type 1).
   • For each original vertex v, add an edge from v to T with capacity equal to cost1[v]. This represents the cost we'd pay if we don't choose type 1 for v (i.e., if v ends up in the T partition/type 2).
3. Add edges for original graph connections:
   • For each original undirected edge (u, v) with cost c, add two directed edges: one from u to v and one from v to u, each with capacity c. This models the idea that if u and v are the same type (same partition), we can't use this edge for connectivity—so we have to "pay" its cost as a penalty (since we'd need alternative paths to keep the graph connected).

Step 2: Compute the Minimum Cut #

Using any standard max-flow algorithm (like Dinic's algorithm, which is efficient for most cases), compute the maximum flow from S to T. By the max-flow min-cut theorem, the value of this max flow equals the capacity of the minimum cut in our auxiliary graph.

This minimum cut partitions our vertices into two sets:

• Nodes connected to S in the residual graph: assign these to type 1 (pay cost1 for each).
• Nodes connected to T: assign these to type 2 (pay cost2 for each).

Step 3: Calculate the Total Minimal Cost #

To get our total cost:

1. Sum the chosen vertex costs: add cost1 for all type 1 vertices, cost2 for all type 2 vertices.
2. Add the cost of all cross-type edges (edges connecting type 1 and type 2 vertices)—these are the edges that keep our graph connected.

Alternatively, you can compute this using the min cut value with a handy formula:

• Let total_all_vertex_costs = sum(cost1[v] + cost2[v] for all v)
• Let total_all_edge_costs = sum(edge cost for all edges)
• Total minimal cost = total_all_vertex_costs + total_all_edge_costs - max_flow_value

This formula works because the max flow represents the maximum savings we get by choosing optimal vertex types and using cross-type edges (avoiding penalties for same-type edges and choosing cheaper vertex costs).

Alternative: MST Variant for Smaller Graphs #

If your graph is small and you prefer a more intuitive approach, you can model this as a modified minimum spanning tree (MST):

1. For each original vertex v, create two nodes: v1 (type 1, cost cost1) and v2 (type 2, cost cost2).
2. Add an edge between v1 and v2 with a very large cost (effectively forcing us to pick only one of the two nodes per original vertex).
3. For each original edge (u, v) with cost c, add edges between u1 and v2 (cost c) and u2 and v1 (cost c)—these represent valid cross-type connections.
4. Compute the MST of this new graph. The MST will include exactly one node per original vertex and the minimal set of cross-type edges to keep everything connected, giving you the total minimal cost.

Why This Works #

The min cut approach efficiently encodes our binary vertex choices and connectivity constraints. By turning the problem into a flow network, we leverage well-optimized algorithms to find the optimal partition. The MST variant is more intuitive for small graphs but scales less well than flow algorithms for large graphs.

内容的提问来源于stack exchange，提问作者Daxter