max flow or max matching

Mek · Post by **Mek** » Sun Feb 06, 2005 4:05 pm

please tell me some uva problems with max flow or max matching application to train my skill

gvcormac · Post by **gvcormac** » Sun Feb 06, 2005 5:24 pm

10746 Crime Wave - The Sequel
670 The Dog Task
10511 Councilling
663 Sorting Slides
753 A plug for Unix
563 Crimewave
2354 What's in a name?

Adrian Kuegel · Post by **Adrian Kuegel** » Sun Feb 06, 2005 8:10 pm

and:
259 Software Allocation
820 Internet Bandwidth
10080 Gopher II
10092 The Problem with the Problemsetter
10122 Mysterious Mountain
10330 Power Transmission
10380 Shogi Tournament
10779 Collectors Problem
10804 Gopher Strategy

Mek · Post by **Mek** » Sun Feb 06, 2005 11:46 pm

Thanks, I'll try to solve them

greco · Post by **greco** » Mon Feb 21, 2005 12:49 pm

IMO max flow kicks ass

so I started to solve this problems. I didn't have any trouble solving Software Allocation, but I haven't solved #563 Crimewave yet.

First I thought that there will be a graph with s*a vertices, the source will be connected to the banks and the vertices on the border will be connected to a destination. Finding a max flow on this graph means that there will not be 2 robbers going on the same road, but it doesn't stop them going through the same intersection, but on different routes.

Can anybody explain his/her solution? Thanks.

misof · Post by **misof** » Mon Feb 21, 2005 1:52 pm

greco wrote:First I thought that there will be a graph with s*a vertices, the source will be connected to the banks and the vertices on the border will be connected to a destination. Finding a max flow on this graph means that there will not be 2 robbers going on the same road, but it doesn't stop them going through the same intersection, but on different routes.

A standard trick to introduce capacity limits on vertices is to split each vertex v into two vertices v_1, v_2. All edges that lead to v will lead to v_1, all edges from v will leave from v_2. Add an edge from v_1 to v_2 with the capacity limit for the original vertex. (In this case the capacity of the new edge will be 1.)

Note that I don't know whether this algorithm really solves the problem you mention, I just answer your question on limiting the flow through vertices.

greco · Post by **greco** » Mon Feb 21, 2005 2:05 pm

Thanks about the advice... I thought about something like this but the graph already has 2.500 nodes, and the length of the source is already... big.

I don't know if I can write the code with your advice... if I do write it I don't know if I can debug it... and if I debug it I don't know if it will fit the time constraint.

I was wondering if someone thought of another way to use the max flow...

Thanks anyway.