Maximum flow (Dinic)

ゼミでやったので, 今更だけど最大フローを実装してみる.
O(n^2m)になってるはずだけど長い..

#!/usr/bin/env perl
use strict;
use warnings;
#use Carp::Assert;
use Data::Dumper;

package Edge;
sub new {
  my ($class, $source, $target, $weight) = @_;
  my $self = {
    source => int($source),
    target => int($target),
    weight => $weight,
  };
  return bless $self, $class;
}

package Vertex;
sub new {
  my ($class, $id) = @_;
  my $self = {
    id    => int($id),
    edges => [],
  };
  return bless $self, $class;
}

package main;
use List::Util;

my $INF = 1e+20;
sub augment { # O(nm)
  my ($levelGraph, $flow, $source, $tink) = @_;
  my $dfs;
  $dfs = sub { # return new flow
    my ($v, $minCap) = @_;
    return $minCap if ($v->{id} == $tink);
    while (@{$v->{edges}}) {
      my $newflow = $dfs->($levelGraph->[$v->{edges}[0]{target}],
        List::Util::min ($minCap, $v->{edges}[0]{weight}));
      if ($newflow) {
        my $e = $v->{edges}[0];
        $flow->[$e->{source}][$e->{target}] += $newflow;
        $e->{weight} -= $newflow;
        shift @{$v->{edges}} unless ($e->{weight});
        return $newflow;
      } else {
        shift @{$v->{edges}};
      }
    }
    return 0;
  };
  my $ret;
  $ret += $dfs->($levelGraph->[$source], $INF) while(@{$levelGraph->[$source]{edges}});
  #assert($ret) if DEBUG;
  return $ret;
}

sub makeLevelGraph { # O(n^2)
  my ($flow, $N, $capacity, $source, $tink) = @_;
  my (@level, @levelGraph, @queue);
  $level[$_] = 0 for(0..$N-1);
  $levelGraph[$_] = new Vertex($_) for(0..$N-1);
  push @queue, $levelGraph[$source];
  $level[$source] = 1;
  while(@queue) { # bfs
    my $v = shift @queue;
    return \@levelGraph if ($v->{id} == $tink);
    for(my $i=0; $i<$N; $i++) {
      my $residualCapacity = $capacity->[$v->{id}][$i]
        - List::Util::max($flow->[$v->{id}][$i] - $flow->[$i][$v->{id}], 0);
      if(($level[$i] == 0 or $level[$i] == $level[$v->{id}]+1)
          and $residualCapacity > 0) {
        push @{$v->{edges}}, new Edge($v->{id}, $i, $residualCapacity);
        if($level[$i] == 0) {
          $level[$i] = $level[$v->{id}]+1;
          push @queue, $levelGraph[$i];
        }
      }
    }
  }
  return 0;
}

sub maxFlow {
  my ($N, $edges, $source, $tink) = @_;
  my ($capacity, $flow); #adjacent matrix
  my $totalFlow;
  for(my $i=0;$i<$N;$i++) {
    for(my $j=0;$j<$N;$j++) {
      $flow->[$i][$j]=0;
      $capacity->[$i][$j]=0;
    }
  }

  foreach my $e (@$edges) {
    $capacity->[$e->{source}][$e->{target}]+=$e->{weight};
  }
  while(my $levelGraph=makeLevelGraph($flow, $N, $capacity, $source, $tink)) {
    #at most n times
    $totalFlow+=augment($levelGraph, $flow, $source, $tink);
  }
  return $totalFlow;
}