Help about MAX Flow

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
anwar
New poster
Posts: 1
Joined: Thu Aug 07, 2003 10:50 am
Location: Dhaka,Bangladesh
Contact:

Help about MAX Flow

Post by anwar »

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

Daniel Chia
New poster
Posts: 12
Joined: Mon Jul 29, 2002 3:04 pm
Contact:

Post by Daniel Chia »

Problem 10030 can be solved by max flow.

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang »

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

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Post by Whinii F. »

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. :)
JongMan @ Yonsei

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Post by hank »

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
New poster
Posts: 4
Joined: Fri Sep 26, 2003 9:29 am
Location: Singapore
Contact:

Post by Steven Halim »

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
The Lord is my shepherd ~ Psalms 23

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry »

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

horape
New poster
Posts: 49
Joined: Sat Sep 13, 2003 3:18 pm
Location: Buenos Aires

Post by horape »

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
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede »

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
Kalo mau kaya, buat apa sekolah?

Post Reply

Return to “Algorithms”