how to know when to apply max flow(ford_fulkerson algo)

general
,
1

How to know that when to apply the above algo like in http://www.spoj.com/problems/NETADMIN/
As here I thought its sufficient to apply bfs/dfs but the above algo needs to be applied i guess.:stuck_out_tongue:
plzz help

2

When it comes to network flow algorithms it’s really hard to classify the problem as “maxflow problem”. You basically have either two choices, at least in my opinion:

  1. Learn all the mathematical theorems that go with network flow and matching and then you’ll most likely know when to apply them, though none of the programmers i know use this method.
  2. Solve enough of those type of problems so that you can guess from experience that you need to some sort of flow algorithm.

Also look into topcoder’s tutorial on this subject,


Read anything with the word “flow” in tittle.

The site i learned the algorithm from (a long with most of the people i know) is USACO:
http://cerberus.delos.com:791/usacotext2?a=Uj92yD6t8mr&S=flow