Help about MAX Flow

anwar · Post by **anwar** » Tue Aug 12, 2003 12:47 pm

Is there any problem that can be solved by MAX FLOW Alogorithm.

Daniel Chia · Post by **Daniel Chia** » Fri Aug 15, 2003 8:29 am

Problem 10030 can be solved by max flow.

junjieliang · Post by **junjieliang** » Fri Aug 15, 2003 12:37 pm

That would be 10330 "Power Transmission", not 10030...

Whinii F. · Post by **Whinii F.** » Fri Aug 15, 2003 12:56 pm

To name few problems come to mind..

10092 The Problem with the Problem Setter
10380 Shogi Tournament
563 Crimewave (Which is identical to an exercise in CLR network flow chapter)

Of course there should be more.

hank · Post by **hank** » Sun Aug 24, 2003 7:20 am

Whinii F. wrote:To name few problems come to mind..

10380 Shogi Tournament <=why do you think it is a maxflow problem?

Of course there should be more.

Hi,Whinii F..
Can you give me some hints about problem 10380?
thanks in advance.

Steven Halim · Post by **Steven Halim** » Wed Oct 01, 2003 7:14 pm

Some Max Flow problems:

10092 - the problem with the problem setter
10249 - the grand dinner (btw, Max Flow will be too slow to pass TLE)

Some Max Bipartite Matching problem (Max Flow variant):

670 - the dog task
753 - a plug for unix
10080 - gopher 2

There may be several more... I'm still searching...
refer to my website for a more complete problem classifications
(the list is still (and will always) growing)

http://www.comp.nus.edu.sg/~stevenha/pr ... egory.html

---
Steven

Larry · Post by **Larry** » Wed Mar 10, 2004 3:07 am

What can be optimized about the Edmond-Karp? I've gotten TLE on Gopher II and it's running really slowly..

horape · Post by **horape** » Wed Mar 10, 2004 5:57 am

Larry wrote:What can be optimized about the Edmond-Karp? I've gotten TLE on Gopher II and it's running really slowly..

Change algorithm

Lift to front is lots faster.

Saludos,

titid_gede · Post by **titid_gede** » Wed Mar 10, 2004 10:41 am

i use ford fulkerson with DFS for augmenting path (worse than edmond -karp ) and got AC in not more than 0.4 sec. perhaps something wrong with your implementation?

regards,
titid