네트워크에 대한 최대 흐름 계산

Question

트리와 유사한 네트워크의 최대 흐름을 계산 (선형 시간)하는 알고리즘을 찾을 수 있습니다. 즉, 싱크 (및 관련 에지)를 제거하면 나무.

Answer 1

Ford-Fulkerson은 O (E * f)입니다. 여기서 E는 가장자리 수이고 f는 최대 유량이며, 문제의 E 또는 f에 상한선이있는 경우 선형으로 간주됩니다.

maxf(s) { 
    if (s == sink) return s.in_capacity; 
    ret = 0; 
    foreach(c in children(s)) ret += maxf(c); 
    return min(ret, s.in_capacity); 
} 

사용의 동일한 소스 (우리는 소스가 무한대의 in_capacity이 있다고 가정)에와 초기 전화 :

Answer 2

예, 바로 다음과 같은 뭔가를 실행합니다.