最大流

今日のSRM399で最大流の問題が出てて、結構よく出てライブラリと持っていないとその場で書くのは難しいのでコードをここに張っておく。

class MaximumFlow {
  int size;
  int flow[][];
  int capacity[][];
  int q[];
  public MaximumFlow(int capacity[][]){
    size = capacity.length;
    flow = new int[size][size];
    this.capacity = capacity;
    q = new int[size];
  }
  void init(){
    for(int i = 0 ; i < flow.length ; i++)
      Arrays.fill(flow[i], 0);
  }
  /**
   * 入口から出口までの最大フローを返す
   * @param src 入口
   * @param dst　出口
   * @return 最大フロー
   */
  public int maximumflow(int src , int dst){
    int total = 0;
    int prev[] = new int[size];
    init();
    while(augment(src, dst, prev)){
      int inc = Integer.MAX_VALUE;
      for(int j = dst ; prev[j] != j ; j = prev[j]){
        inc = Math.min(inc, residu(prev[j], j));
      }
      for(int j = dst ; prev[j] != j ; j = prev[j]){
        flow[prev[j]][j] += inc;
        flow[j][prev[j]] -= inc;
      }
      total += inc;
    }
    return total;
  }
  
  private boolean augment(int src, int dst, int[] prev) {
    int top  = 0;
    int tail = 0;
    q[tail++] = src;
    Arrays.fill(prev, -1);
    prev[src] = src;
    while(top < tail && prev[dst] < 0){
      int cp = q[top++];
      for(int i = 0 ; i < size ; i++){
        if(prev[i] < 0 && residu(cp , i) > 0){
          prev[i] = cp;
          if(i == dst)return true;
          q[tail++] = i;
        }
      }
    }
    return prev[dst] >= 0;
  }
  private int residu(int s , int t){
    return capacity[s][t] - flow[s][t];
  }
}

ついでに二部グラフの最大マッチングのコードもはっておく

  int bipartite_matching(boolean adj[][], int leftSize) {
    int match = 0;
    int matchTo[] = new int[adj.length];
    Arrays.fill(matchTo, -1);
    boolean visited[] = new boolean[adj.length];
    for (int u = 0; u < leftSize; u++) {
      Arrays.fill(visited, false);
      if (augment(adj, u, matchTo, visited))
        match++;
    }
    return match;
  }

  boolean augment(boolean adj[][], int u, int matchTo[], boolean visited[]) {
    if (u < 0)
      return true;
    for(int i = 0 ; i < adj[u].length ; i++){
      if(adj[u][i] && !visited[i]){
        visited[i] = true;
        if (augment(adj, matchTo[i], matchTo, visited)) {
          matchTo[u] = i;
          matchTo[i] = u;
          return true;
        }        
      }
    }
    return false;
  }