Maximum Flow dengan algoritma Ford-Fulkerson. Menggunakan python-graph: http://code.google.com/p/python-graph/

ford-fulkerson.py

from pygraph.classes.digraph import digraph

dgr = digraph()   # Graph
flow = {}

# Semacam DFS
def find_path(source, sink, path):
	global flow

	if(source == sink):
		return path
	
	for neighbors in dgr.neighbors(source):
		edge = (source, neighbors)
		residual = dgr.edge_weight(edge) - flow[edge]
		if residual > 0 and not edge in path:
			result = find_path(neighbors, sink, path + [edge])
			if result != None:
				return result

def ford_fulkerson(source, sink):
	global flow

	# All flow are zero
	for edge in dgr.edges():
		flow[edge] = 0
		flow[edge[::-1]] = 0
	
	path = find_path(source, sink, [])
	while path != None:
		residuals = [dgr.edge_weight(edge) - flow[edge] for edge in path]
		flow_min = min(residuals)
		for edge in path:
			flow[edge] = flow[edge] + flow_min
			flow[edge[::-1]] = flow[edge[::-1]] - flow_min
		path = find_path(source, sink, [])
	
	return sum(flow[(source, neighbors)] for neighbors in dgr.neighbors(source))
		
			

def main():
	# Input test case
	# Number of vertices
	n = int(raw_input())

	for i in range(n):
		dgr.add_nodes(str(i))

	# Number of edges
	e = int(raw_input())

	# Edge definition
	for i in range(e):
		new_edge = raw_input().split()
		if dgr.has_edge((str(new_edge[0]), str(new_edge[1]))):
			dgr.set_edge_weight((str(new_edge[0]), str(new_edge[1])), int(new_edge[2]))
		else:
			dgr.add_edge((str(new_edge[0]), str(new_edge[1])), int(new_edge[2]))

		if dgr.has_edge((str(new_edge[1]), str(new_edge[0]))):
			pass
		else:
			dgr.add_edge((str(new_edge[1]), str(new_edge[0])), 0)
				
	
	# Define source and sink
	source = raw_input()
	sink = raw_input()

	# Search for maximum flow using ford-fulkerson algorithm
	print ford_fulkerson(source, sink)

	# Done

main()
		
		

testcase

TC1 Result = 5

6
8
0 1 3
0 2 3
1 2 2
1 3 3
2 4 2
4 5 3
3 4 4
3 5 2
0
5

TC2 Result = 23

6
10
0 1 16
0 2 13
1 2 10
1 3 12
2 1 4
2 4 14
3 2 9
3 5 20
4 3 7
4 5 4
0
5