読者です 読者をやめる 読者になる 読者になる

8VC Venture Cup 2017 - Elimination Round F. PolandBall and Gifts

競技プログラミング Codeforces

問題

http://codeforces.com/contest/755/problem/F

プレゼント交換をします。iさんはp[i]さんにプレゼントを渡します。複数の人が同じ人にプレゼントを渡すことはありません。

K人がプレゼントを忘れました。プレゼントを忘れた人はプレゼントを受け取れません。また、プレゼントを忘れられた人も当然プレゼントを受け取れません。

プレゼントを受け取れない人数の最大値と最小値を求めてください。

解法

以下のような5人のサイクルを考えます。
A->B->C->D->E->A

このとき、Aがプレゼントを忘れると、AとB両方がプレゼントを受け取ることができなくなります。

2人忘れたとき、AとBが忘れたパターンと、AとCが忘れたパターンで、最終的な受け取れない人数が変わります。このように考えると最大値は簡単に求まります。

最小値は、サイクルの長さの集合 {L_i} からいくつか選んでKが作れるかを判定する部分和問題に帰着できます。(作れれば最小値はK、そうでなければK+1)

touristさんのコードをみるとこのナップザック問題をbitsetで高速に解いていて面白かったので真似しました。

コード

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.BitSet;
import java.util.NoSuchElementException;

public class F {
  /**
   * @param cnt cnt[l] := 大きさlのものの個数
   * @param K   作りたい大きさ
   * @return Kが作れるかどうか
   */
  private boolean knapsack(int[] cnt, int K) {
    int N = cnt.length - 1;
    BitSet bitSet = new BitSet();
    bitSet.set(N);
    for (int i = 1; i <= N; i++) {
      if (cnt[i] == 0) continue;
      int j = 1;
      while (cnt[i] > 0) {
        j = Math.min(j, cnt[i]);
        int u = i * j;
        bitSet.or(bitSet.get(u, bitSet.length()));
        cnt[i] -= j;
        j *= 2;
      }
    }
    return bitSet.get(N - K);
  }

  private void solve(FastScanner in, PrintWriter out) {
    int N = in.nextInt();
    int K = in.nextInt();
    boolean[] vis = new boolean[N];
    int[] p = new int[N];
    for (int i = 0; i < N; i++) {
      p[i] = in.nextInt() - 1;
    }
    int[] cnt = new int[N + 1];
    int solo = 0, pair = 0;
    for (int i = 0; i < N; i++) {
      if (vis[i]) continue;
      int cur = i;
      int length = 0;
      while (!vis[cur]) {
        vis[cur] = true;
        length++;
        cur = p[cur];
      }
      cnt[length]++;
      solo += length % 2;
      pair += length / 2;
    }

    int min = K;
    if (!knapsack(cnt, K)) {
      min++;
    }

    int max = 0;
    max += 2 * Math.min(K, pair);
    K -= Math.min(K, pair);
    max += Math.min(K, solo);

    out.println(min + " " + max);
  }

  public static void main(String[] args) {
    FastScanner in = new FastScanner();
    PrintWriter out = new PrintWriter(System.out);
    new F().solve(in, out);
    out.close();
  }

  private static class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int bufferLength = 0;

    private boolean hasNextByte() {
      if (ptr < bufferLength) {
        return true;
      } else {
        ptr = 0;
        try {
          bufferLength = in.read(buffer);
        } catch (IOException e) {
          e.printStackTrace();
        }
        if (bufferLength <= 0) {
          return false;
        }
      }
      return true;
    }

    private int readByte() {
      if (hasNextByte()) return buffer[ptr++];
      else return -1;
    }

    private static boolean isPrintableChar(int c) {
      return 33 <= c && c <= 126;
    }

    private void skipUnprintable() {
      while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;
    }

    boolean hasNext() {
      skipUnprintable();
      return hasNextByte();
    }

    public String next() {
      if (!hasNext()) throw new NoSuchElementException();
      StringBuilder sb = new StringBuilder();
      int b = readByte();
      while (isPrintableChar(b)) {
        sb.appendCodePoint(b);
        b = readByte();
      }
      return sb.toString();
    }

    long nextLong() {
      if (!hasNext()) throw new NoSuchElementException();
      long n = 0;
      boolean minus = false;
      int b = readByte();
      if (b == '-') {
        minus = true;
        b = readByte();
      }
      if (b < '0' || '9' < b) {
        throw new NumberFormatException();
      }
      while (true) {
        if ('0' <= b && b <= '9') {
          n *= 10;
          n += b - '0';
        } else if (b == -1 || !isPrintableChar(b)) {
          return minus ? -n : n;
        } else {
          throw new NumberFormatException();
        }
        b = readByte();
      }
    }

    double nextDouble() {
      return Double.parseDouble(next());
    }

    double[] nextDoubleArray(int n) {
      double[] array = new double[n];
      for (int i = 0; i < n; i++) {
        array[i] = nextDouble();
      }
      return array;
    }

    double[][] nextDoubleMap(int n, int m) {
      double[][] map = new double[n][];
      for (int i = 0; i < n; i++) {
        map[i] = nextDoubleArray(m);
      }
      return map;
    }

    public int nextInt() {
      return (int) nextLong();
    }

    public int[] nextIntArray(int n) {
      int[] array = new int[n];
      for (int i = 0; i < n; i++) array[i] = nextInt();
      return array;
    }

    public long[] nextLongArray(int n) {
      long[] array = new long[n];
      for (int i = 0; i < n; i++) array[i] = nextLong();
      return array;
    }

    public String[] nextStringArray(int n) {
      String[] array = new String[n];
      for (int i = 0; i < n; i++) array[i] = next();
      return array;
    }

    public char[][] nextCharMap(int n) {
      char[][] array = new char[n][];
      for (int i = 0; i < n; i++) array[i] = next().toCharArray();
      return array;
    }

    public int[][] nextIntMap(int n, int m) {
      int[][] map = new int[n][];
      for (int i = 0; i < n; i++) {
        map[i] = nextIntArray(m);
      }
      return map;
    }
  }
}

AtCoder Regular Contest 067 E - Grouping

競技プログラミング AtCoder

解法

dp[i][member] := i人をmember人未満のグループに分ける組合せ

としてDPします。

コード

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.NoSuchElementException;
import java.util.Scanner;

public class Main {
  private final long MOD = (long) (1e9 + 7);

  public class Combination {
    private long[] fact;
    private long[] invFact;

    public Combination(int max) {
      long[] inv = new long[max + 1];
      fact = new long[max + 1];
      invFact = new long[max + 1];
      inv[1] = 1;
      for (int i = 2; i <= max; i++) inv[i] = inv[(int) (MOD % i)] * (MOD - MOD / i) % MOD;
      fact[0] = invFact[0] = 1;
      for (int i = 1; i <= max; i++) fact[i] = fact[i - 1] * i % MOD;
      for (int i = 1; i <= max; i++) invFact[i] = invFact[i - 1] * inv[i] % MOD;
    }

    public long get(int x, int y) {
      return fact[x] * invFact[y] % MOD * invFact[x - y] % MOD;
    }
  }

  private void solve(Scanner in, PrintWriter out) {
    int N = in.nextInt();
    int A = in.nextInt();
    int B = in.nextInt();
    int C = in.nextInt();
    int D = in.nextInt();

    Combination combination = new Combination(N);

    long[][] dp = new long[N + 2][N + 2];
    dp[0][A] = 1;

    //dp[i][member] := i人を使ってmember人未満のチームで分ける方法
    for (int i = 0; i <= N; i++) {
      for (int member = A; member <= B; member++) {
        if (dp[i][member] <= 0) continue;
        dp[i][member + 1] += dp[i][member];
        dp[i][member + 1] %= MOD;

        long d = dp[i][member];
        for (int num = 1; num <= D; num++) {
          if (i + num * member > N) break;
          int remain = N - (i + (num - 1) * member);
          d *= combination.get(remain, member);
          d %= MOD;
          if (num < C) continue;
          long e = d * combination.invFact[num];
          e %= MOD;
          dp[i + num * member][member + 1] += e;
          dp[i + num * member][member + 1] %= MOD;
        }
      }
    }

    out.println(dp[N][B + 1]);

  }

  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    PrintWriter out = new PrintWriter(System.out);
    new Main().solve(in, out);
    in.close();
    out.close();
  }
}

Codecraft-17 and Codeforces Round #391 (Div. 1 + Div. 2, combined) D. Felicity's Big Secret Revealed

Codeforces 競技プログラミング

問題

http://codeforces.com/contest/757/problem/D

0と1からなるn文字の文字列が与えられます。この文字列の好きな位置(先頭や末尾も含むN+1個)に仕切りを入れることができます。仕切りはいくつ入れても構いませんが、同じ位置に2個以上入れることはできません。仕切りを入れ終わったら、仕切りに挟まれている数字を10進数になおし、setに入れます。setの最大の数字をmとした時に、setに1〜mが全て含まれているような仕切りの入れ方をvalidとします。validな仕切りの入れ方をmod 1e9+7 で答えてください。

解法

nが75以下なので、mは最大でも20であることが分かります。

次のようなbitDPを考えます。

dp[pos][status] := pos文字目まで見た時に、[1, 20] の数字を含む状態のbitが status であるような組合せ

どこから始めても良いので初期状態は dp[i][0]=1 (0<=i

コード

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;

public class D {
  private final int MOD = (int) (1e9 + 7);
  private void solve(FastScanner in, PrintWriter out) {
    int N = in.nextInt();
    String S = in.next();
    int M = 1 << 20;
    int[][] dp = new int[N + 1][M];
    for (int pos = 0; pos < N; pos++) {
      dp[pos][0] = 1;
    }
    for (int pos = 0; pos < N; pos++) {
      int cur = 0;
      for (int end = pos + 1; end <= N; end++) {
        cur = cur * 2 + (S.charAt(end - 1) - '0');
        if (cur > 20) break;
        if (cur == 0) continue;
        for (int state = 0; state < M; state++) {
          int next = state | (1 << (cur - 1));
          dp[end][next] += dp[pos][state];
          dp[end][next] %= MOD;
        }
      }
    }

    long ans = 0;
    for (int end = 0; end <= N; end++) {
      for (int h = 1; h <= 20; h++) {
        int state = (1 << h) - 1;
        ans += dp[end][state];
        ans %= MOD;
      }
    }
    out.println(ans);
  }

  public static void main(String[] args) {
    FastScanner in = new FastScanner();
    PrintWriter out = new PrintWriter(System.out);
    new D().solve(in, out);
    out.close();
  }

  private static class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int bufferLength = 0;

    private boolean hasNextByte() {
      if (ptr < bufferLength) {
        return true;
      } else {
        ptr = 0;
        try {
          bufferLength = in.read(buffer);
        } catch (IOException e) {
          e.printStackTrace();
        }
        if (bufferLength <= 0) {
          return false;
        }
      }
      return true;
    }

    private int readByte() {
      if (hasNextByte()) return buffer[ptr++];
      else return -1;
    }

    private static boolean isPrintableChar(int c) {
      return 33 <= c && c <= 126;
    }

    private void skipUnprintable() {
      while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;
    }

    boolean hasNext() {
      skipUnprintable();
      return hasNextByte();
    }

    public String next() {
      if (!hasNext()) throw new NoSuchElementException();
      StringBuilder sb = new StringBuilder();
      int b = readByte();
      while (isPrintableChar(b)) {
        sb.appendCodePoint(b);
        b = readByte();
      }
      return sb.toString();
    }

    long nextLong() {
      if (!hasNext()) throw new NoSuchElementException();
      long n = 0;
      boolean minus = false;
      int b = readByte();
      if (b == '-') {
        minus = true;
        b = readByte();
      }
      if (b < '0' || '9' < b) {
        throw new NumberFormatException();
      }
      while (true) {
        if ('0' <= b && b <= '9') {
          n *= 10;
          n += b - '0';
        } else if (b == -1 || !isPrintableChar(b)) {
          return minus ? -n : n;
        } else {
          throw new NumberFormatException();
        }
        b = readByte();
      }
    }

    double nextDouble() {
      return Double.parseDouble(next());
    }

    double[] nextDoubleArray(int n) {
      double[] array = new double[n];
      for (int i = 0; i < n; i++) {
        array[i] = nextDouble();
      }
      return array;
    }

    double[][] nextDoubleMap(int n, int m) {
      double[][] map = new double[n][];
      for (int i = 0; i < n; i++) {
        map[i] = nextDoubleArray(m);
      }
      return map;
    }

    public int nextInt() {
      return (int) nextLong();
    }

    public int[] nextIntArray(int n) {
      int[] array = new int[n];
      for (int i = 0; i < n; i++) array[i] = nextInt();
      return array;
    }

    public long[] nextLongArray(int n) {
      long[] array = new long[n];
      for (int i = 0; i < n; i++) array[i] = nextLong();
      return array;
    }

    public String[] nextStringArray(int n) {
      String[] array = new String[n];
      for (int i = 0; i < n; i++) array[i] = next();
      return array;
    }

    public char[][] nextCharMap(int n) {
      char[][] array = new char[n][];
      for (int i = 0; i < n; i++) array[i] = next().toCharArray();
      return array;
    }

    public int[][] nextIntMap(int n, int m) {
      int[][] map = new int[n][];
      for (int i = 0; i < n; i++) {
        map[i] = nextIntArray(m);
      }
      return map;
    }
  }
}

Codeforces Round #390 (Div. 2) D. Fedor and coupons

Codeforces 競技プログラミング

問題

http://codeforces.com/contest/754/problem/D

[l, r] のような範囲の組が N 個あります。このうちK個を選び、K個すべてが重なる範囲を最大にしたいです。最大値と、その時選ぶ範囲のidを出力してください。

解法

非想定解法っぽい Treap

コード

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.NoSuchElementException;
import java.util.Random;

public class D {
  private void solve(FastScanner in, PrintWriter out) {
    int N = in.nextInt();
    int K = in.nextInt();

    long[] l = new long[N];
    long[] r = new long[N];
    long min = 0;
    for (int i = 0; i < N; i++) {
      l[i] = in.nextInt();
      r[i] = in.nextInt();
      min = Math.min(min, l[i]);
    }
    for (int i = 0; i < N; i++) {
      l[i] -= min;
      r[i] -= min;
      l[i] = l[i] * 2 * N + i;
      r[i] = r[i] * 2 * N + i + N;
    }

    long[][] events = new long[2 * N][2];
    for (int i = 0; i < N; i++) {
      events[2 * i][0] = l[i];
      events[2 * i][1] = i;
      events[2 * i + 1][0] = r[i];
      events[2 * i + 1][1] = -i - 1;
    }
    Arrays.sort(events, (o1, o2) -> {
      if (o1[0] == o2[0]) return Long.compare(o1[1], o2[1]);
      return Long.compare(o1[0], o2[0]);
    });

    Treap treap = new Treap();
    long from = -1;
    long max = 0;
    long[] range = null;
    int coupons = 0;
    for (long[] e : events) {
      int i = (int) e[1];
      if (i >= 0) {
        coupons++;
        treap.insert(l[i]);
        if (coupons == K) {
          from = l[i] / (2 * N);
        }
      } else {
        i = -(i + 1);
        long tr = r[i] / (2 * N);
        long tl = l[i] / (2 * N);
        if (tl <= from && coupons >= K) {
          long curRange = tr - from + 1;
          if (max < curRange) {
            max = curRange;
            range = new long[]{from, tr};
          }
          treap.erase(l[i]);
          if (coupons > K) {
            long kth = treap.rank(K - 1);
            from = kth / (2 * N);
          }
        } else {
          treap.erase(l[i]);
        }
        coupons--;
      }
    }
    out.println(max);
    if (max == 0) {
      for (int i = 0; i < K; i++) {
        out.print((i + 1) + " ");
      }
      out.println();
      return;
    }

    for (int i = 0; i < N; i++) {
      long L = l[i] / (2 * N);
      long R = r[i] / (2 * N);
      if (L <= range[0] && range[1] <= R) {
        out.print((i + 1) + " ");
        K--;
        if (K == 0) break;
      }
    }
    out.println();
  }

  public class Treap {
    Random random = new Random();

    private class Node {
      Node left, right;
      long key;
      int priority;
      int count;

      Node(long key) {
        this.key = key;
        priority = random.nextInt();
        left = null;
        right = null;
        count = 1;
      }
    }

    private Node root = null;

    public void clear() {
      root = null;
    }

    public boolean isEmpty() {
      return count(root) == 0;
    }

    private int count(Node n) {
      return n == null ? 0 : n.count;
    }

    private void update(Node c) {
      c.count = 1 + count(c.left) + count(c.right);
    }

    private Node leftRotate(Node c) {
      Node r = c.right;
      c.right = r.left;
      r.left = c;
      update(c);
      return r;
    }

    private Node rightRotate(Node c) {
      Node l = c.left;
      c.left = l.right;
      l.right = c;
      update(c);
      return l;
    }

    private Node insert(Node c, long key) {
      if (c == null) return new Node(key);
      if (c.key < key) {
        c.right = insert(c.right, key);
        if (c.right.priority < c.priority) c = leftRotate(c);
      } else {
        c.left = insert(c.left, key);
        if (c.left.priority < c.priority) c = rightRotate(c);
      }
      update(c);
      return c;
    }

    private Node getMinNode(Node c) {
      while (c.left != null) c = c.left;
      return c;
    }

    private Node erase(Node c, long key) {
      if (key == c.key) {
        if (c.left == null) return c.right;
        if (c.right == null) return c.left;

        Node minNode = getMinNode(c.right);
        c.key = minNode.key;
        c.right = erase(c.right, minNode.key);
      } else {
        if (c.key < key) c.right = erase(c.right, key);
        else c.left = erase(c.left, key);
      }
      update(c);
      return c;
    }

    public void insert(long key) {
      if (contains(key)) return;
      root = insert(root, key);
    }

    public void erase(long key) {
      root = erase(root, key);
    }

    public int size() {
      return count(root);
    }

    public boolean contains(long key) {
      return find(root, key) >= 0;
    }

    public int find(long key) {
      return find(root, key);
    }

    private int find(Node c, long key) {
      if (c == null) return -1;
      if (c.key == key) return count(c.left);
      if (key < c.key) return find(c.left, key);
      int pos = find(c.right, key);
      if (pos < 0) return pos;
      return count(c.left) + 1 + pos;
    }

    private Node rank(Node c, int rank) {
      while (c != null) {
        int leftCount = count(c.left);
        if (leftCount == rank) return c;
        if (leftCount < rank) {
          rank -= leftCount + 1;
          c = c.right;
        } else {
          c = c.left;
        }
      }
      return null;
    }

    public long rank(int rank) {
      if (root == null)
        throw new NullPointerException();
      Node r = rank(root, rank);
      if (r == null)
        throw new NullPointerException();
      return r.key;
    }

  }

  public static void main(String[] args) {
    FastScanner in = new FastScanner();
    PrintWriter out = new PrintWriter(System.out);
    new D().solve(in, out);
    out.close();
  }

  private static class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int bufferLength = 0;

    private boolean hasNextByte() {
      if (ptr < bufferLength) {
        return true;
      } else {
        ptr = 0;
        try {
          bufferLength = in.read(buffer);
        } catch (IOException e) {
          e.printStackTrace();
        }
        if (bufferLength <= 0) {
          return false;
        }
      }
      return true;
    }

    private int readByte() {
      if (hasNextByte()) return buffer[ptr++];
      else return -1;
    }

    private static boolean isPrintableChar(int c) {
      return 33 <= c && c <= 126;
    }

    private void skipUnprintable() {
      while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;
    }

    boolean hasNext() {
      skipUnprintable();
      return hasNextByte();
    }

    public String next() {
      if (!hasNext()) throw new NoSuchElementException();
      StringBuilder sb = new StringBuilder();
      int b = readByte();
      while (isPrintableChar(b)) {
        sb.appendCodePoint(b);
        b = readByte();
      }
      return sb.toString();
    }

    long nextLong() {
      if (!hasNext()) throw new NoSuchElementException();
      long n = 0;
      boolean minus = false;
      int b = readByte();
      if (b == '-') {
        minus = true;
        b = readByte();
      }
      if (b < '0' || '9' < b) {
        throw new NumberFormatException();
      }
      while (true) {
        if ('0' <= b && b <= '9') {
          n *= 10;
          n += b - '0';
        } else if (b == -1 || !isPrintableChar(b)) {
          return minus ? -n : n;
        } else {
          throw new NumberFormatException();
        }
        b = readByte();
      }
    }

    double nextDouble() {
      return Double.parseDouble(next());
    }

    double[] nextDoubleArray(int n) {
      double[] array = new double[n];
      for (int i = 0; i < n; i++) {
        array[i] = nextDouble();
      }
      return array;
    }

    double[][] nextDoubleMap(int n, int m) {
      double[][] map = new double[n][];
      for (int i = 0; i < n; i++) {
        map[i] = nextDoubleArray(m);
      }
      return map;
    }

    public int nextInt() {
      return (int) nextLong();
    }

    public int[] nextIntArray(int n) {
      int[] array = new int[n];
      for (int i = 0; i < n; i++) array[i] = nextInt();
      return array;
    }

    public long[] nextLongArray(int n) {
      long[] array = new long[n];
      for (int i = 0; i < n; i++) array[i] = nextLong();
      return array;
    }

    public String[] nextStringArray(int n) {
      String[] array = new String[n];
      for (int i = 0; i < n; i++) array[i] = next();
      return array;
    }

    public char[][] nextCharMap(int n) {
      char[][] array = new char[n][];
      for (int i = 0; i < n; i++) array[i] = next().toCharArray();
      return array;
    }

    public int[][] nextIntMap(int n, int m) {
      int[][] map = new int[n][];
      for (int i = 0; i < n; i++) {
        map[i] = nextIntArray(m);
      }
      return map;
    }
  }
}

2016年を振り返って2017年の目標を決める

その他

2016年の良かったこと

  • ジムに行って筋トレした
  • Kaggleに参加した
  • ICDMで発表した
  • ルンバを買った
  • ガルパンを観た
  • Reactをやった
  • 会社を辞めなかった

2016年の良くなかったこと

2017年の目標

Push-Relabel による最大フローアルゴリズム

資料 競技プログラミング

はじめに

この記事はCompetitive Programming (その2) Advent Calendar 2016 - Adventarの23日目の記事として書かれました。

最初に、一般的なフローネットワークについて触れてます。これは始点と終点を除く頂点について、入ってくるフローと出ていくフローが常に等しい状態であるもので、Ford-Fulkerson 法などを理解するために必要です。最小カット最大フローの定理についても触れます。

次に、条件を緩和して過剰フローを許したプリフローについて考えます。高さ関数制約を導入してプッシュ操作と再ラベル操作を定め、Generic-Push-Relabel のアルゴリズムを考えます。プリフローネットワークに対して処理をしていくと最終的に最大フローが得られることを確認し、再ラベル操作、飽和プッシュ操作、非飽和プッシュ操作の回数の上界を調べます。

さらに、開栓操作を加えた Relabel-To-Front を考えることで、計算量をO(V^3)に改善します。ここに Highest-Label Rule を導入して、 O(V^2 \sqrt{E})まで改善します。

最後に実装も載せました。

この記事に書いてあることは "Introduction to Algorithms" という本にそのまま書いてあります。

フローネットワーク

各辺  (u, v) \in E が、容量 c(u,v) \geqq 0 を持つ有向グラフである。入り口 s と出口 t が設定されている。

非負の値を取る量  f(u,v) を頂点 u から頂点 v へのフローと呼ぶ。

フローは以下の 2 条件を満たす。

  • 容量制限: 全ての  u,v \in V に対して、 0 \leqq f(u,v) \leqq c(u,v) でなければならない。
  • フロー保存則: 全ての  u \in V - \{s,t \}に対して、\sum_{v \in V} f(v,u)= \sum_{v \in V} f(u, v)でなければならない。
    • 頂点 u に入ってくるフローと、頂点 u から出ていくフローの量が等しい。

最大フロー問題は s から t への最大の値を持つフローを求める問題である。

逆平行辺

f:id:kenkoooo:20161021042256j:plain

逆平行辺を持つネットワークは簡単に逆平行辺を持たないグラフに構成し直すことが出来るので、議論を簡明にするため逆平行辺を禁止することにする。

複数の入口と出口

f:id:kenkoooo:20161021041928j:plain

複数の入口があっても超入口を作ってそこから各入口に容量無限の辺を張れば、入口 1 つのネットワークとして扱える。出口についても同様。

残余ネットワーク

辺 (u, v) に追加でどのくらいフローを流すことが出来るかを残余容量  c_f(u, v)=c(u,v)-f(u,v) で表す。

 (v,u) \in E にフローが f(v, u) 流れているとき、フローを削減できることを表現するため、 c_f(u,v)=f(v,u) と表せる。

これをまとめると、


c_f(u,v) = \begin{cases}
    c(u,v)-f(u,v) & (u,v) \in E \\
    f(v,u) & (v,u) \in E \\
    0 & それ以外
  \end{cases}

増加

f(u,v) 流れているフローを変化させることを考える。f を G におけるフロー、f' を残余容量からなる残余ネットワーク  G_f のフローとすると、変化後のフローは以下のように表される。



(f \uparrow f')(u,v) = \begin{cases}
f(u,v) + f'(u,v) - f'(v,u)  & (u,v) \in E \\
0 & それ以外
\end{cases}

補題 26.1

 |f \uparrow f'| = |f|+|f'| である。

証明

まず、容量制限を満たすことを示す。
  \begin{eqnarray} 
(f \uparrow f')(u,v) &=& f(u,v)+f'(u,v)-f'(v,u) \\
&\geqq& f(u,v)+f'(u,v)-f(u,v) \\
&=& f'(u,v) \\
&\geqq& 0

\end{eqnarray}

  \begin{eqnarray} 
(f \uparrow f')(u,v) &=& f(u,v)+f'(u,v)-f'(v,u) \\
&\leqq& f(u,v)+f'(u,v) \\
&\leqq& f(u,v)+c_f(u,v) \\
&=& f(u,v) +c(u,v) -f(u,v) \\
&=& c(u,v)

\end{eqnarray}

http://www.cs.dartmouth.edu/~thc/clrs-bugs/pages/pp-718-720.pdf


全てのu\in V について以下の式が成り立つことを示す。
 \sum_{v \in V}(f\uparrow f')(u,v)- \sum_{v \in V}(f\uparrow f')(v,u) =  \sum_{v \in V}f(u,v)-\sum_{v \in V}f(v,u)+\sum_{v \in V}f'(u,v)-\sum_{v \in V}f'(v,u)


u から出る辺のもう一方の端点の集合を V_1(u) = \{ v:(u,v) \in E \}と表す。
また、u へ向かう辺のもう一方の端点の集合を V_2(u) = \{ v:(v,u) \in E \}と表す。

G には逆平行辺を含まれないので、 V_1(u) \cap V_2(u)=\emptyset


\begin{cases}
(f \uparrow f')(u,v)>0 & v \in V_1(u) \\
(f \uparrow f')(v,u)>0 & v \in V_2(u)
\end{cases}



 \begin{eqnarray} 
 \sum_{v \in V}(f\uparrow f')(u,v)&-& \sum_{v \in V}(f\uparrow f')(v,u)\\
&=&  \sum_{v \in V_1(u)}(f\uparrow f')(u,v)- \sum_{v \in V_2(u)}(f\uparrow f')(v,u) \\
&=&  \sum_{v \in V_1(u)}(f(u,v)+f'(u,v)-f'(v,u))- \sum_{v \in V_2(u)}(f(v,u)+f'(v,u)-f'(u,v)) \\ 
&=&  \sum_{v \in V_1(u)}f(u, v) -  \sum_{v \in V_2(u)}f(v, u) +  \sum_{v \in V_1(u)}f'(u, v) +  \sum_{v \in V_2(u)}f'(u, v) -  \sum_{v \in V_1(u)}f'(v,u) -  \sum_{v \in V_2(u)}f'(v, u)  \\ 
&=&  \sum_{v \in V_1(u)}f(u, v) -  \sum_{v \in V_2(u)}f(v, u) +  \sum_{v \in V_1(u) \cup V_2(u)}f'(u, v)  -  \sum_{v \in V_1(u) \cup V_2(u)}f'(v,u)  
 \end{eqnarray}



 \begin{eqnarray} 
 |f \uparrow f'| 
&=& \sum_{v \in V}(f \uparrow f')(s,v) -\sum_{v \in V}(f \uparrow f')(v,s) \\
&=& \sum_{v \in V}f(s,v)- \sum_{v \in V}f(v, s) + \sum_{v \in V}f'(s,v)- \sum_{v \in V}f'(v, s) \\
&=& |f|+|f'|
 \end{eqnarray}

増加可能経路

残余ネットワーク  G_f 上での s から t への経路。

増加可能経路 p の各辺に沿って増やすことの出来るフローの最大値を p の残余容量とし、以下のように定義する。
 c_f(p) =min\{c_f(u,v): (u, v) は p 上にある  \}

補題 26.2

関数f_pを以下のように定義する。

 f_p(u, v)=
\begin{cases}
c_f(p) & (u,v) が p 上にあるとき \\
0 & それ以外
\end{cases}

このとき、 f_p G_f のフローで |f_p|=c_f(p) > 0 である。

 | f \uparrow f_p| =|f|+|f_p| > |f| より、 f_p f に加えると、より最大値に近い f を得られる。

フローネットワークのカット

V を  s \in S t \in T を満たす S と T=V-S に分割する。これをカット (S, T) とする。

カット(S,T) と交差する純フローを
 f(S,T) =\sum_{u\in S} \sum_{v\in T}f(u,v) -\sum_{u\in S} \sum_{v\in T}f(v,u)
と定義する。

カットの容量は c(S,T)=\sum_{u\in S}\sum_{v\in T} c(u,v)である。

最小カットは、カット(S, T)の中で、容量が最小のカットである。

補題 26.4

カット(S, T)と交差する純フローは f(S, T)=|f| である。

証明


 \begin{eqnarray} 
 | f | &=& \sum_{v \in V}f(s,v) - \sum_{v \in V}f(v,s)\\
&=& \sum_{v \in V}f(s,v) - \sum_{v \in V}f(v,s) +\sum_{u \in S-\{s\} }\big(  \sum_{v\in V}f(u,v)- \sum_{v\in V}f(v,u)  \big)\\
&=& \sum_{v \in V}f(s,v) - \sum_{v \in V}f(v,s) +\sum_{u \in S-\{s\} }  \sum_{v\in V}f(u,v)- \sum_{u \in S-\{s\} }\sum_{v\in V}f(v,u) \\
&=& \sum_{v \in V} \big( f(s,v) +\sum_{u \in S-\{s\} } f(u,v)\big) - \sum_{v \in V} \big( f(v,s) +\sum_{u \in S-\{s\} } f(v,u)\big) \\
&=& \sum_{v \in V} \sum_{u\in S}f(u, v)- \sum_{v \in V} \sum_{u\in S}f(v, u) \\
&=& \sum_{v \in S} \sum_{u\in S}f(u, v) + \sum_{v \in T} \sum_{u\in S}f(u, v) - \sum_{v \in S} \sum_{u\in S}f(v, u) - \sum_{v \in T} \sum_{u\in S}f(v, u)  & (V=S \cup T かつ S \cap T = \emptyset だから)\\
&=& \sum_{v \in T} \sum_{u\in S}f(u, v) - \sum_{v \in T} \sum_{u\in S}f(v, u)  +\big(  \sum_{v \in S} \sum_{u\in S}f(u, v) - \sum_{v \in S} \sum_{u\in S}f(v, u)  \big) \\
&=& \sum_{v \in T} \sum_{u\in S}f(u, v) - \sum_{v \in T} \sum_{u\in S}f(v, u)  \\
&=& f(S,T)
 \end{eqnarray}

系 26.5

G の任意のフロー f の値は G の任意のカット容量によって上から抑えられる。

証明


 \begin{eqnarray} 
 |f| &=& f(S,T)\\
&=& \sum_{v \in T} \sum_{u\in S}f(u, v) - \sum_{v \in T} \sum_{u\in S}f(v, u)\\
&\leqq& \sum_{v \in T} \sum_{u\in S}f(u, v) \\
&\leqq& \sum_{v \in T} \sum_{u\in S}c(u, v) \\
&=&c(S, T)
 \end{eqnarray}

定理 26.6 最大フロー最小カットの定理

  1. fはGの最大フローである。
  2. 残余ネットワーク Gf は増加可能経路を含まない。
  3. Gのあるカット(S,T)に対して|f|=c(S,T) である。
証明

最大フローであるにも関わらず増加可能経路を持つと仮定すると、f_p が定まり、|f| より値が大きいGのフローが得られるので矛盾する。

Gf が増加可能経路を持たないとき、Gfにはsからtへの道が存在しない。

 S=\{ v \in V: G_f に s から v への道が存在する \}, T=V-S と定義する。

明らかに s\in S であり、 G_fにはsからtへの道が存在しないので t\not\in Sである。よって、この分割(S,T)はカットである。

 u\in Sかつ v\in T かつ  (u,v) \in E であるようなu, v を考える。
f(u,v)\not= c(u,v)ならば(u,v)\in E_f であり、 v\in Sとなり矛盾する。よってf(u,v)= c(u,v)である。

f(v,u)\not=0ならば c_f(u,v)=f(v,u)(u,v)\in E_f だからv\in Sとなり矛盾する。よって f(v,u)=0


 \begin{eqnarray} 
f(S,T) &=& \sum_{u\in S}\sum_{v\in T}f(u,v)-\sum_{u\in S}\sum_{v\in T}f(v,u) \\
&=& \sum_{u\in S}\sum_{v\in T}c(u,v)-\sum_{u\in S}\sum_{v\in T}0 \\
&=&c(S,T)
 \end{eqnarray}

全てのカット(S, T) に対して|f| \leqq c(S,T) である。よって|f| = c(S,T) はfが最大フローであるための十分条件である。

過剰量とプリフロー

今までは頂点にフローを溜め込むことができない条件のみを考えてきた。

頂点 u に流入するフローと頂点 u から流出するフローの合計が等しかった。

\begin{eqnarray}
 \sum_{v \in V-\{s\}} f(v,u) - \sum_{v \in V-\{s\}}f(u,v) = 0
\end{eqnarray}

これを緩和して、流入量が流出量を超えることが出来るものとする。

\begin{eqnarray}
 \sum_{v \in V-\{s\}} f(v,u) - \sum_{v \in V-\{s\}}f(u,v) \geq 0
\end{eqnarray}

このような条件でのフローをプリフローと呼ぶ。

この過剰量を e(u) とする。

u\in V-\{s\} について、

\begin{eqnarray}
e(u) =  \sum_{v \in V} f(v,u) - \sum_{v \in V}f(u,v) 
\end{eqnarray}

 e(u)>0 となるような頂点  u \in V-\{s,t\} をオーバーフロー頂点と呼ぶ。

高さ関数

h(s)=|V|, h(t)=0であり、残余辺(u,v)\in E_fについて、h(u)\leq h(v)+1 が成り立つような高さ関数 h を考える。

プッシュ操作

以下の条件を満たす残余辺 (u, v) について、u から v にフローをプッシュする。

\begin{eqnarray}
\begin{cases}
h(u)=h(v)+1 \\
c_f(u,v)>0 \\
e(u) > 0
\end{cases}
\end{eqnarray}

Push(u, v)
    # 適用条件: u がオーバーフロー頂点で、c_f(u, v) > 0 かつ h(u) = h(v) + 1
    df = min(e(u), c_f(u, v))
    if (u, v) in E
        (u, v).f = (u, v).f + df
    else
        (v, u).f = (v, u).f - df
    e(u) -= df
    e(v) += df

プッシュ後に c_f(u,v)=0 となるようなプッシュを飽和プッシュと呼ぶ。

再ラベル操作

e(u)>0 かつ  (u,v) \in E_f の全ての v について  h(u) \leq h(v) であるとき、u の高さを上げる。

Relabel(u)
    # 適用条件: u がオーバーフロー頂点、かつ、h(u) <= h(v)
    h(u) = 1 + min([h(v) for (u, v) in E_f])

基礎アルゴリズム

Initialize-Preflow(G, s)
    for v in V
        h(v) = 0
        e(v) = 0
    for (u, v) in E
        (u, v).f = 0
    h(s) = |V|
    for v in G[s]
        (s, v).f = c(s, v)
        e(v) = c(s,v)
        e(s) -= c(s, v)

これによって s から出る全ての辺に容量上限までフローを流す。
つまり、s から出る辺は残余グラフに含まれなくなる。
よって全ての残余辺  (u,v) \in E_f について  h(u) \leq h(v)+1が成り立つ。
(全てのu \in V-\{s\}について h(u)=0だから)

Generic-Push-Relabel(G)
    Initialize-Preflow(G, s)
    while 適用可能な push か relabel がある
        適用可能な push か relabel を選び、実行する

Push-Relabel の正当性

アルゴリズムが停止したときプリフロー f が最大フローであることと、アルゴリズムが停止することを示す。

補題 26.14

u がオーバーフロー頂点であれば、push か relabel が実行可能である。

証明

u から push が実行可能でない場合、全ての残余辺  (u, v) \in E_f について、 h(u) < h(v)+1 である。
このとき、 h(u) \leq h(v) であり、relabel が実行可能である。

補題26.15

Generic-Push-Relabel の実行中、h(u) は減少しない。

証明

h(u) は relabel 以外では変化せず、relabel では適用のたびに必ず 1 以上増える。

補題26.16

Generic-Push-Relabel は h を高さ関数として維持する。

証明

初期状態では h が高さ関数制約を満たしている。

u から出る辺 (u, v) を考える。
Relabel(u) を行った後はh(u) \leq h(v)+1 が保証される。

u に入る辺 (w, u) を考える。
Relabel(u) の前に  h(w) \leq h(u) +1 が成立していたならば、操作後は  h(w) < h(u) +1 が成立する。

よって Relabel(u) は高さ制約を維持する。

Push(u, v) を実行することを考える。

Push(u, v) によって f(v, u) が減少するとき、 c_f(v,u) が増加する。
これはE_f に (v, u) が加わると考えられる。
このときh(u)=h(v)+1 だからh(v)=h(u)-1< h(u)+1である。
新しい残余辺 (v, u) について  h(v) \leq h(u)+1 が成り立つ。

Push(u, v) によって  c_f(u,v) が減少するとき、E_f から (u, v) が取り除かれると考える。
このときは、制約が取り除かれるので、再び h は高さ関数である。

補題26.17

f をプリフローとする。このとき残余グラフ G_f には s から t への道はない。

証明

矛盾を導くために G_f における s から t への道  p = < v_0,v_1,...,v_k > が存在すると仮定する。
v_0=s, v_k=tである。
一般性を失うことなく k<|V| と仮定する。

 i=0,1,...,k-1に対して(v_i,v_{i+1}) \in E_fである。
 i=0,1,...,k-1に対してh(v_i)\leq h(v_{i+1}) +1である。
よって h(s)\leq h(t)+k である。
ここでh(t)+k=0+k=kだからh(s)\leq k <|V|となり、高さ関数制約h(s)=|V|に矛盾する。

補題26.18

Generic-Push-Relabel を実行して停止したとき、プリフロー f は最大フローである。

証明

Initialize-Preflow 実行後の f はプリフローである。

while ループ内では push と relabel が実行される。
relabel は f に影響しない。
push 実行前に f がプリフローならば、実行後も f はプリフローである。

補題 26.14 より、停止したときはV-\{s,t\}にオーバーフロー頂点は存在しない。
よってv \in V-\{s,t\}について e(v)=0 である。
よって、プリフロー f はフローである。

補題 26.17 より、残余ネットワークG_fには s から t への道が存在しない。
よってフロー f は最大フローである。

Generic-Push-Relabel の解析

補題 26.19

f をプリフローとする。この時、残余ネットワークG_fの任意のオーバーフロー頂点 u から s への単純道が存在する。

証明

オーバーフロー頂点 x について、U=\{v: G_f において xからvへの単純道がある\}とする。
s が U に含まれることを示す。

矛盾を導くためにs \not\in Uを仮定する。
 \overline{U}=V-Uとする。


\begin{eqnarray}
e(u) =  \sum_{v \in V} f(v,u) - \sum_{v \in V}f(u,v) 
\end{eqnarray}
より、

\begin{eqnarray}
\sum_{u\in U}e(u) &=& \sum_{u\in U}\big(  \sum_{v \in V} f(v,u) - \sum_{v \in V}f(u,v) \big) \\
 &=& \sum_{u\in U}\big(  \big(  \sum_{v \in U} f(v,u) + \sum_{v \in \overline{U}} f(v,u)  \big) - \big(  \sum_{v \in U} f(u,v) + \sum_{v \in \overline{U}} f(u,v)  \big) \big) \\
 &=& \sum_{u\in U}\sum_{v \in U}f(v,u)+ \sum_{u\in U}\sum_{v \in \overline{U}}f(v,u)-\sum_{u\in U}\sum_{v \in U}f(u,v)- \sum_{u\in U}\sum_{v \in \overline{U}}f(u,v)\\
 &=&  \sum_{u\in U}\sum_{v \in \overline{U}}f(v,u)- \sum_{u\in U}\sum_{v \in \overline{U}}f(u,v)\\
\end{eqnarray}

e(x)>0, x \in Uかつ、s以外のすべての頂点が非負の過剰を持ち、s\not\in Uだから、\sum_{u\in U}e(u)>0である。

したがって

\begin{eqnarray}
 \sum_{u\in U}\sum_{v \in \overline{U}}f(v,u)- \sum_{u\in U}\sum_{v \in \overline{U}}f(u,v) > 0
\end{eqnarray}

フローは非負だから

\begin{eqnarray}
 \sum_{u\in U}\sum_{v \in \overline{U}}f(v,u) > 0
\end{eqnarray}

よってf(v',u')>0となる u' \in U, v' \in \overline{U} が存在する。
よって残余ネットワークG_fには残余辺(u',v')が存在する。

よって道 x\leadsto u' \to v' が存在する。これは v' \in U となり矛盾。

補題 26.20

Generic-Push-Relabel 実行中はすべての頂点 u で  h(u) \leq 2|V| -1が成り立つ。

証明

h(s)=|V|, h(t)=0 なので、 u \in V-\{s,t\} となる頂点 u について考える。

u から s への単純道  p=< v_0, ..., v_k > にを考える。ここではv_0=u, v_k=sである。pは単純道なのでk< |V|-1である。

h(v_i)\leq h(v_{i+1})+1だから

 h(v_0)=h(v_0) \leq h(v_k)+k \leq h(s)+(|V|-1)=2|V|-1

系 26.21

relabel の回数は頂点当たり高々2|V|-1回である。

証明

各頂点の高さ関数 h(u) は最大で 2|V|-1回上がる。はい。

補題 26.22

飽和プッシュ回数は2|V||E|回未満である。

証明

u から v への飽和プッシュが発生するとき、h(v)=h(u)-1である。
同様に v から u への飽和プッシュが発生するとき、h(v)=h(u)+1である。
つまり、u から v への飽和プッシュが起こった後、v から u への飽和プッシュが起こるまでに h(v) は少なくとも 2 増加する。
h(v) の最大値は 2|V|-1 なので、u と v の間に起こる飽和プッシュの回数は 2|V| 回未満であり、辺の本数を考えると全体で 2|V||E| 未満である。

補題 26.23

非飽和プッシュ回数は4|V|^2(|V|+|E|)回である。

証明

ポテンシャル関数\Phiを定義する。


\begin{eqnarray}
\Phi = \sum_{v :e(v)>0} h(v)
\end{eqnarray}

頂点 u の relabel によって \Phi は高々 2|V|-1 だけ増加する。
頂点 u からの飽和プッシュによって \Phi は高々 2|V|-1 だけ増加する。

頂点 u から v への非飽和プッシュを考える。
この操作により e(u)=0 となるので、h(u) は和の対象から外れ、\Phi は正確に h(u) だけ減少する。
v がもともとオーバーフロー頂点だったとき、\Phi の増加量は 0 である。
v が新たにオーバーフロー頂点となる場合、 \Phi は h(v) だけ増加する。
h(u)=h(v)+1 だから、\Phi は少なくとも 1 減少する。

relabel 回数の上界が (2|V|-1)(|V|-2) 回、飽和プッシュ回数の上界が 2|V||E| 回、だから、relabel の上界を 2|V|^2 として、 \Phiの増加量の上界は
 (2|V|)(2|V|^2)+(2|V|)(2|V||E|) = 4|V|^2(|V|+|E|) である。

\Phi は非飽和プッシュによって減少するので、非飽和プッシュ回数の上界は4|V|^2(|V|+|E|)である。

許容辺

c_f(u, v) > 0 かつ h(u) == h(v) + 1 を満たすとき、辺(u, v)を許容辺という。

補題26.27

辺(u,v)へのプッシュ操作push(u,v)は新たな許容辺を作らない。

証明

(u,v)へプッシュ可能なとき、h(u)=h(v)+1である。(u,v)へのプッシュ操作によって唯一新たに残余辺(v,u)が生成しうるが、h(v)=h(u)-1であるためこれは許容辺ではない。よってプッシュ操作では新たな許容辺は作られない。

補題26.28

頂点uがオーバーフロー頂点で、uから外に向かう許容辺がなければrelabel(u)が適用できる。また、この操作の後、少なくとも1本はuから外へ向かう許容辺が存在し、uに入る許容辺は存在しない。

証明

uがオーバーフロー頂点なら、補題26.14よりプッシュかリラベル操作ができる。uから外へ向かう許容辺がないときプッシュ操作ができないので、リラベル操作ができる。リラベル操作終了後は h(u) = 1+\{h(v) : (u,v)E_f\}となり、辺(u,v)が許容辺となるような頂点vが存在し、uからvへ向かう許容辺が出来る。

リラベル操作終了後に、vからuに入る許容辺(v,u)が存在していると仮定すると、h(v)=h(u)+1であることから、リラベル操作終了前にはh(v)>h(u)+1であったことになる。しかし、高さが2以上違う頂点の間には残余辺が存在しないので、矛盾する。

オーバーフロー頂点での開栓

Discharge(u):
    while e(u) > 0:
        it = G[u].next()
        if it is None:
            Relabel(u)
            it = G[u].iterator()
        elif c_f(u, v) > 0 and h(u) == h(v) + 1:
            Push(u, v)
        else:
            it = G[u].next()

補題26.29

discharge(u)がrelabel(u)を呼び出すとき、uに対してリラベル操作が可能である。

証明

relabel(u)が呼び出されるとき、uから外に向かう許容辺が存在しないことを示す。

relabel(u)が呼び出されるとき、uから外へ向かう辺のうち許容辺であるものは全てプッシュ操作が適用された後である。補題26.27より、これらのプッシュ操作およびグラフ内で起こった別のプッシュ操作によって新たに許容辺が作られることはない。別の discharge(v)によってrelabel(v)が起こった場合、補題26.28よりvに入る許容辺が新たに生成されることはないため、uから外へ出る許容辺が新たに生成されることはない。

よって、relabel(u)が呼び出されるとき、uから外に向かう許容辺が存在しない。

アルゴリズム

Relabel-To-Front(s, t):
    Initialize-Preflow()
    L = []
    for u in G:
        if u != s and u != t:
            L.append(u)
    it = L.iterator()
    u = it.next()
    while u != None:
        old = h(u)
        Discharge(u)
        if h(u) > old:
            u を L の先頭に移動
            it = L.iterator()
        u = it.next()

任意の順番で頂点を見ていって、dischargeして高さが変わっているならその頂点をリストの先頭に持っていってリスタート、という感じである。

定理26.30

計算量はO(V^3)だよ。

証明

リラベル操作とリラベル操作の間をフェーズと呼ぶことにする。

リラベル操作はO(V^2)回行われるので、O(V^2)回のフェーズがある。dischargeがrelabel操作を呼び出さないとき、dischargeはリストを順番に見ていくので、高々|V|回行われる。一方、dischargeがrelabelを呼び出すと、その次に実行されるdischargeは別のフェーズのものとなる。よって、各フェーズで呼び出されるdischargeは高々|V|回であり、dischargeの総呼び出し回数はO(V^3)回である。

飽和プッシュの回数は全部でO(VE)である。非飽和プッシュが行われるとdischargeは直ちに終了する。よって非飽和プッシュの総実行回数はO(V^3)である。

よって、計算量はO(V^3)だよ。

補題4.2

非飽和プッシュ回数はO(V^2\sqrt{E})

証明

ポテンシャル関数

\begin{eqnarray}
\Phi = \sum_{u :e(u)>0} |\{v | h(v)\leq h(u)\}|
\end{eqnarray}を定義する。

リラベル操作や飽和プッシュ操作によって \Phi は最大Vだけ増加する。リラベル操作は全部でO(V^2)回、飽和プッシュ操作は全部でO(VE)回行われるので、全体で \Phiの増加量はO(V^2E)である。

オーバーフロー頂点のうち、高さが最大のものをuとする。h(u)を変化させるリラベルの間に起こった非飽和プッシュたちをフェーズと呼ぶことする。リラベル操作を行ったり、uの過剰フローを次の高さの頂点に全てプッシュし終えたりするとフェーズは終了する。各頂点ごとに必ず1回は非飽和プッシュが存在し、最大でも 4V^2回のフェーズがある(リラベル操作の2倍の回数)。

k回以上の非飽和プッシュが行われるフェーズをbigとし、それ以外のフェーズをsmallとする。smallフェーズでは最大でk回の非飽和プッシュが行われるので、全体で 4kV^2回行われる。bigフェーズでは高さが最大の頂点がk個以上存在するので、1回の非飽和プッシュで少なくともポテンシャルはk減少する。全体で \Phiの増加量はO(V^2E)であるから、bigフェーズの非飽和プッシュは全体でO(V^2E/k)回である。よってbigとsmallの非飽和プッシュの回数は合計でO(V^2E/k + V^2k)である。ここで k=\sqrt{E}とすると、O(V^2 \sqrt{E})となる。

実装

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;

public class RelabelToFront {
  class Edge {
    int from, to, rev;
    long flow, cap;
    Edge(int from, int to, long cap, int rev) {
      this.from = from;
      this.to = to;
      this.cap = cap;
      this.rev = rev;
      this.flow = 0;
    }
  }

  private int N;
  private ArrayList<ArrayList<Edge>> graph = new ArrayList<>();
  private long[] excess;
  private int[] height;
  private int[] seen;
  private PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(o -> -o[0]));

  RelabelToFront(int N) {
    this.N = N;
    for (int i = 0; i < N; i++) graph.add(new ArrayList<>());
    excess = new long[N];
    height = new int[N];
    seen = new int[N];
  }

  public void addEdge(int from, int to, long cap) {
    graph.get(from).add(new Edge(from, to, cap, graph.get(to).size()));
    graph.get(to).add(new Edge(to, from, 0, graph.get(from).size() - 1));
  }

  private void push(Edge e) {
    int u = e.from;
    int v = e.to;

    long send = Math.min(excess[u], e.cap - e.flow);
    e.flow += send;
    graph.get(v).get(e.rev).flow -= send;
    excess[u] -= send;
    excess[v] += send;

    if (excess[v] > 0) queue.add(new int[]{height[v], v});
    if (excess[u] > 0) queue.add(new int[]{height[u], u});
  }

  private void relabel(int u) {
    int minHeight = N * 2;
    for (Edge e : graph.get(u))
      if (e.cap - e.flow > 0)
        minHeight = Math.min(minHeight, height[e.to]);
    height[u] = minHeight + 1;

    queue.add(new int[]{height[u], u});
  }

  private void discharge(int u) {
    while (excess[u] > 0) {
      if (seen[u] < graph.get(u).size()) {
        Edge e = graph.get(u).get(seen[u]);
        if (e.cap - e.flow > 0 && height[u] == height[e.to] + 1)
          push(e);
        else
          seen[u] += 1;
      } else {
        relabel(u);
        seen[u] = 0;
      }
    }
  }

  public long maxFlow(int source, int sink) {
    height[source] = N;
    for (Edge e : graph.get(source)) {
      excess[source] += e.cap;
      push(e);
    }

    while (!queue.isEmpty()) {
      int[] q = queue.poll();
      int u = q[1];
      if (u == source || u == sink) continue;
      discharge(u);
    }

    long maxFlow = 0;
    for (Edge e : graph.get(source)) maxFlow += e.flow;

    return maxFlow;
  }
}

終わりに

くぅ~疲れましたw これにて完結です!
実は、会社の輪読会で最大フローの章を担当したのが始まりでした
本当はRelabel-To-Frontに辿り着く前に力尽きてしまったのですが←
ご厚意を無駄にするわけには行かないので流行りのアドベントカレンダーで挑んでみた所存ですw
以下、Mi_Sawaさんのみんなへのメッセジをどぞ

「動的木を使うともっと速くなります」

追記

退学を支える技術

その他

この記事は退学 Advent Calendar 2016 - Adventarの22日目の記事です。

アドベントカレンダーに投稿されている記事を見ると、退学した人間の自分語りか退学する予定の自分語りの記事しかないので、ここでは少し趣向を変えて、退学の技術的なノウハウを共有したいと思います。

退学とは

退学とはそもそもなんでしょうか。放校や除籍など広義の退学を含む場合もありますが、ここでは退学願を提出することを退学とします。

退学願の入手法

退学願はどのように入手すればよいのでしょうか。もしかしたら事務室に行けば手に入るかもしれませんが、退学したいわけですし、できれば学校に行かずに入手したいところです。

https://www.k.u-tokyo.ac.jp/j/syllabus/tai.pdf

学校によっては、このようにインターネットで退学願をダウンロードすることができます。これで人間と会話せずに退学願を書くことができそうです。

スタンプラリー

f:id:kenkoooo:20161222065824p:plain

退学願を見てまず目に入ってくるのは、専攻長や指導教員と書かれた長方形です。書類の右上にある長方形には押印すべしというルールが説明無しにまかり通っていますが、これも例外ではなく、この長方形内に指定された人物に印鑑を押してもらう必要があります。

写真の例では、指導教員ならびに専攻長から印鑑を押して貰う必要があります。つまり、少なくとも2回はスタンプラリーをする必要があるわけです。しかしながら、退学したいのに悠長にスタンプラリーに興じている場合ではないということは学校側も百も承知で、実はスタンプを集める必要はありません。ある程度の規模の学校であれば退学者を出すことにも慣れているため、このスタンプラリーも自動化されています。スタンプが押されていない状態の退学願をそのまま事務室に提出しても、それが専攻長や指導教員のもとに巡っていき、スタンプが押された状態になって教務課へ自動的に提出されるのです。

退学の理由

f:id:kenkoooo:20161222070549p:plain

学籍番号や個人情報を埋めると、その次に理由を書くスペースが与えられます。この理由に何を書いても受理されるとは思いますが、経済的困窮などと書いておくと、あとで述べるような救済措置が施される場合があります。

退学願の提出のタイミング

学校にもよりますが、退学願は学期開始の1ヶ月前までに提出する必要があります。例えば、冬学期は10月1日に開始するので、その前に退学する場合は、8月31日までに提出しなければなりません。また、東京大学の場合、退学届を提出すると職員の方が勝手に授業料免除申請を取り下げてくださいます。

冷静に考えると、退学予定者の授業料を免除する義理はないので、気持ちは分からなくはないのですが、例えば「夏学期は授業料免除して、10月1日に開始する冬学期の前に退学するため、8月31日付けで退学する」というプランで退学願を提出すると、夏学期の授業料免除申請を、経済的な条件などが免除基準をクリアしていようが関係なく、申請をいつの間にか取り下げてきます。これがなかなかの罠で、先に職員に手の内を見せてしまったために、免除される予定の27万円を払う羽目になります。これを避けるために、授業料免除の通知が来たことを確認してから、退学希望日ギリギリの日程で提出する必要があります。

タイムマシン

万が一、払う予定のない授業料を払う事になってしまった場合、タイムマシンを使うことができます。これは奥の手で、「どうしても授業料が払えないので過去に遡って実は既に退学していたことにしてくれ〜」という救済措置です。これについてはここでは話しませんが、消費者金融に行く前に、そういうものも存在することを思い出していただければと思います。

最後に

退学する際に気をつけるべきことは、払う予定のないお金がかからないかどうか、ということです。特に、退学願を出す時は脳内物質が大変なことになっているでしょうから、意識的に冷静になって、制度を調べながら対処する必要があります。

皆さんの確実な退学を応援いたします。