I'm doing a course in algorithms and I'm stuck on this problem.

Given a set of vertices on a grid. Every vertex has a coordinate (x,y). An source and a sink has been given. From every vertex there can only be drawn 4 types of edges.

O1: The edge can be drawn from v1 to v2 if v1.x=v2.x or v1.y==v1.y.

O2: The edge can be drawn from v1 to v2 if the euclidean distance between v1 and v2 is the largest possible.

O3: The edge can be drawn from v1 to v2 if there's at least 2 vertices on the line segment between v1 and v2.

O4: The edge can be drawn from v1 to the sink.

Every vertex has a maximum number for each edge type that can be drawn from it.

Input example for one vertex:

0,1,4,0,2,0 - Is the vertex at coordinate 0,1 where the maximum number of type O1 edges that can be drawn is 4, type O2 is 0, type O3 is 2 and type O4 is 0.

The problem is to find the maximum flow of the graph.

My approach is that if I'm able to generate a weighted directed graph, I can apply Ford-Fulkerson and get the result. I'm able to generate the graph with all possible edges, but I have no idea how to figure out which edges should be drawn to ensure maximum flow (the restriction on the number of edge types from a given vertex is what trips me up).

I assume that every edge have weight 1, in the resulting multigraph, thus making the maximum flow problem well defined.

Example:

0 1 4 0 2 0
2 2 1 2 3 4
4 1 3 1 1 0
4 3 1 0 0 1
6 4 0 0 1 1
9 1 1 0 0 2
9 4 2 0 0 1
9 3 0 0 0 0

Possible edges:

Drawn solution:

I know the answer to this instance of the problem is 5.

CodePudding user response：

Nevermind my previous answer, think I got it:

Start with the complete graph

Re-write each node into five nodes, one input and then one output of each type

Add nodes from the input node to each output node depending on how many edges of that type the original node was allowed to have

Calculate max flow on the translated graph

So if in your original graph you had a node n with n.O1_out outgoing neighbors, n.01_limit limit, n.O2_out, n.O2_limit, etc, you'll translate that into:

• An input node n_input such that all nodes that previously had edges to n now have edges to n_input
• An output node n_O1_output such that n_O1_output has edges to all nodes previously in n.O1_out (repeat for O2, etc)
• n.O1_limit edges (or one edge with n.O1_limit weight) going from n_input to n_O1_output (repeat for O2, etc)

Sorry, this is a pain to describe clearly, but does that make sense?