PKU700問目

PKUの解いた問題数がちょうど700問目になった。
700問目の2112 Optimal Milkingは頂点数がK+C個の重みつき無向グラフが与えられて、1..Kの頂点にミルクマシンが置いてあり、K+1..K+Cの頂点に牛が1匹ずついるときに各牛がミルクマシンに配置させるときに最も動く牛の移動距離を最小にせよという問題。ただしミルクマシンの制約として各ミルクマシンはM匹の牛にしかミルクを提供できないとする。
方針はまず各牛からマシンへの最短距離を求めておく、つぎに最も動く牛の移動距離を固定する、このとき問題は最大流に落とせて、入口から各牛に流量１の辺をはって、各マシンから出口へ流量Mの辺を張る、牛とマシン間には牛とマシン間の距離が固定した距離以下ならば流量1の辺を張る。このときフローをCだけ流せればその移動距離での割り当てが存在することがわかる。あとは最も動く牛の移動距離を二分探索すればよい。
以下はソース

import java.util.*;

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];
  }

  public int maximumflow(int src, int dst) {
    int total = 0;
    int prev[] = new int[size];
    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];
  }
}

public class Main {
  final static long INF = Long.MAX_VALUE / 4;

  static boolean can(int K, int C, int M, long dist[][], long th) {
    int capa[][] = new int[K + C + 2][K + C + 2];
    for (int i = 0; i < K; i++)
      for (int j = 0; j < C; j++)
        if (dist[j + K][i] <= th)
          capa[j + K][i] = 1;
    int src = K + C;
    int dst = K + C + 1;
    for (int i = 0; i < C; i++)
      capa[src][K + i] = 1;
    for (int i = 0; i < K; i++)
      capa[i][dst] = M;
    MaximumFlow mf = new MaximumFlow(capa);
    int res = mf.maximumflow(src, dst);
    return res == C;
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int K = sc.nextInt();
    int C = sc.nextInt();
    int M = sc.nextInt();
    long dist[][] = new long[K + C][K + C];
    for (int i = 0; i < dist.length; i++) {
      for (int j = 0; j < dist.length; j++) {
        dist[i][j] = sc.nextLong();
        if (dist[i][j] == 0 && i != j) {
          dist[i][j] = INF;
        }
      }
    }
    for (int k = 0; k < dist.length; k++)
      for (int i = 0; i < dist.length; i++)
        for (int j = 0; j < dist.length; j++)
          dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
    long low = dist[0][0];
    long high = dist[0][0];
    for (long[] d : dist) {
      for (long l : d) {
        low = Math.min(l, low);
        high = Math.max(l, high);
      }
    }
    while (low < high) {
      long mid = low + (high - low) / 2;
      if (can(K, C, M, dist, mid))
        high = mid;
      else
        low = mid + 1;
    }
    System.out.println(low);
  }
}