{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "toc": "true"
   },
   "source": [
    "# Table of Contents\n",
    " <p><div class=\"lev1 toc-item\"><a href=\"#Recap\" data-toc-modified-id=\"Recap-1\"><span class=\"toc-item-num\">1&nbsp;&nbsp;</span>Recap</a></div><div class=\"lev1 toc-item\"><a href=\"#The-Edmonds-Karp-Algorithm:-Shortest-Augmenting-Paths\" data-toc-modified-id=\"The-Edmonds-Karp-Algorithm:-Shortest-Augmenting-Paths-2\"><span class=\"toc-item-num\">2&nbsp;&nbsp;</span>The Edmonds-Karp Algorithm: Shortest Augmenting Paths</a></div><div class=\"lev1 toc-item\"><a href=\"#Dinic's-Algorithm:-Blocking-Flows\" data-toc-modified-id=\"Dinic's-Algorithm:-Blocking-Flows-3\"><span class=\"toc-item-num\">3&nbsp;&nbsp;</span>Dinic's Algorithm: Blocking Flows</a></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Recap"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "とりあえず、復習がてらFigure 2のグラフの最大流をNetworkXのモジュールを用いて求めてみる。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import networkx as nx\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Figure2のグラフを生成\n",
    "G = nx.DiGraph()\n",
    "G.add_edges_from([('s','v',{'capacity': 1}),\n",
    "                  ('s','w',{'capacity': 100}),\n",
    "                  ('w','v',{'capacity': 1}),\n",
    "                  ('v','t',{'capacity': 100}),\n",
    "                  ('w','t',{'capacity': 1})])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "maximum flow: 3\n",
      "(s, v): 1/1\n",
      "(s, w): 2/100\n",
      "(w, t): 1/1\n",
      "(w, v): 1/1\n",
      "(v, t): 2/100\n"
     ]
    }
   ],
   "source": [
    "flow_value, flows = nx.maximum_flow(G,'s','t')\n",
    "print('maximum flow: {}'.format(flow_value))\n",
    "\n",
    "caps = nx.get_edge_attributes(G, 'capacity')\n",
    "for u in nx.topological_sort(G):\n",
    "    for v, flow in sorted(flows[u].items()):\n",
    "        print('({}, {}): {}/{}'.format(u, v, flow, caps[(u, v)]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "念のため、前回自作したFord Fulkerson algorithmも試してみる。いずれの結果も、the maximum flowが3であることを示している。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "code_folding": [
     6,
     98,
     118
    ],
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#前回作ったやつ\n",
    "import networkx as nx\n",
    "import matplotlib.pyplot as plt\n",
    "from collections import deque\n",
    "import numpy as np\n",
    "\n",
    "def bfsFlowPath(G, s, e):\n",
    "    '''\n",
    "    Search a path from s to t all of whose points have strictly positive capacity.\n",
    "    \n",
    "    Inputs:\n",
    "        G: a graph\n",
    "        s: a start point\n",
    "        e: an end point\n",
    "        each edge has two attributes:\n",
    "            capacity: capacity\n",
    "            flow: its current flow which should be no more than its capacity\n",
    "    Output:\n",
    "        path: a list of edges which represents a path from s to e.\n",
    "        At each edge of the path, its current flow is strictly less than its capacity.\n",
    "        In case there is no path from s to t, return None.\n",
    "    '''\n",
    "\n",
    "    # 過去に訪れた点を記録\n",
    "    # sは最初から入れておく\n",
    "    past = [s]\n",
    "    # pathを記録するためのリスト\n",
    "    path = []\n",
    "\n",
    "    # 全ての点のsからの距離の初期値を無限大に\n",
    "    for p in G.nodes():\n",
    "        G.node[p]['dist'] = float('inf')\n",
    "    \n",
    "    # node s の距離を0に\n",
    "    G.node[s]['dist'] = 0\n",
    "    \n",
    "    # sに隣接する点をqueueに\n",
    "    # queueには、今後訪れるべき点が格納される\n",
    "    queue = deque()\n",
    "    for p in G.successors(s):\n",
    "        # current flow < capacity となるedgeだけをpathの候補に\n",
    "        # flow < capacity となるedge以外は存在しないものとして扱うのと同じ\n",
    "        if G[s][p]['flow'] < G[s][p]['capacity']:\n",
    "            queue.append(p)\n",
    "            \n",
    "    # あとで条件分岐に用いる\n",
    "    numberOfSuccessorsOfSource = len(queue)\n",
    "    \n",
    "    # sに隣接する点の距離を1に\n",
    "    for p in queue:\n",
    "        G.node[p]['dist'] = 1\n",
    "\n",
    "    # BFSを用いてflow < capacityを満たすsからeへのpathがあるのか調べる\n",
    "    # pastに過去に訪れた点を格納\n",
    "    while len(queue)>0:\n",
    "        v = queue.popleft()\n",
    "        if v == e: break\n",
    "        else:\n",
    "            past.append(v)\n",
    "            for p in G.successors(v):\n",
    "                # (過去に訪れていない and flow < capacity)を満たすedge\n",
    "                if ( (not p in past) and ( G[v][p]['flow'] < G[v][p]['capacity']) ):\n",
    "                    if ( not p in queue):\n",
    "                        queue.append(p)\n",
    "                    if G.node[p]['dist'] > G.node[v]['dist'] + 1:\n",
    "                        G.node[p]['dist'] = G.node[v]['dist'] + 1\n",
    "\n",
    "    # sからeへのpathが存在しない場合はNoneを返す\n",
    "    if numberOfSuccessorsOfSource == 0:\n",
    "        v = s\n",
    "    if v != e or v == s:\n",
    "        # print ('There is no path.')\n",
    "        return None\n",
    "    \n",
    "    # 以下、sからeへのpathが存在する場合\n",
    "    # 終点から遡ってpathを形成する\n",
    "    pp = e\n",
    "    while (1):\n",
    "        if pp == s: break\n",
    "            \n",
    "        pred = G.predecessors(pp)\n",
    "        count = 0\n",
    "\n",
    "        for p in pred:\n",
    "            # ここに、flow < capacity の条件を追加\n",
    "            if ( G.node[p]['dist'] == G.node[pp]['dist']-1 and G[p][pp]['flow'] < G[p][pp]['capacity']):\n",
    "                path.insert(0, (p,pp))\n",
    "                pp = p\n",
    "                break\n",
    "            else:\n",
    "                count += 1\n",
    "        \n",
    "        # 条件を満たすedgeがない\n",
    "        if count == len(pred):\n",
    "            break\n",
    "\n",
    "    return path\n",
    "\n",
    "def makeResidualGraph(G):\n",
    "    '''\n",
    "    Input: a graph G\n",
    "    Output: its residual graph Gf\n",
    "    '''\n",
    "    Gf = G.copy()\n",
    "    edgeList = G.edges()\n",
    "    \n",
    "    for edge in edgeList:\n",
    "        # Initialize flow\n",
    "        Gf[edge[0]][edge[1]]['flow'] = 0\n",
    "        \n",
    "        # 逆向きのedgeがないものは追加\n",
    "        if not (edge[1], edge[0]) in edgeList:\n",
    "            Gf.add_edge(edge[1],edge[0])\n",
    "            Gf[edge[1]][edge[0]]['capacity'] = Gf[edge[0]][edge[1]]['flow']\n",
    "            Gf[edge[1]][edge[0]]['flow'] = 0\n",
    "    \n",
    "    return Gf\n",
    "\n",
    "def fordFulkerson(G, s, t):\n",
    "    '''\n",
    "    Inputs:\n",
    "        G: a graph\n",
    "        s: a source vertex\n",
    "        t: a sink vertex\n",
    "    Outputs:\n",
    "        the graph G whose flow was modified by Ford-Fulkerson algorithm\n",
    "        In case there is no path from s to t, return None.\n",
    "    '''\n",
    "\n",
    "    # initialize flows\n",
    "    for e in G.edges():\n",
    "        G[e[0]][e[1]]['flow'] = 0\n",
    "\n",
    "    # Forward edgesを記録\n",
    "    forwardEdges = G.edges()\n",
    "    \n",
    "    # Residual Graphの作成\n",
    "    Gf = makeResidualGraph(G)\n",
    "    \n",
    "    # そもそもGにおいてsからtへのパスがあるのか確認\n",
    "    path = bfsFlowPath(G, s, t)\n",
    "    if path == None:\n",
    "        print (\"There is no path from \" + str(s) + \" to \"+ str(t) )\n",
    "        return None\n",
    "    \n",
    "    # Gにおいてsからtへのパスがある場合\n",
    "    while(1):\n",
    "        # これ以上パスがみつからない場合は最適なのでそこでループを打ち切る\n",
    "        path = bfsFlowPath(Gf, s, t)\n",
    "        if path == None:\n",
    "            break\n",
    "\n",
    "        # まだパスがある（最適でない）場合\n",
    "        else:\n",
    "            # path上のedgeについて、capacity - flowの最小値を調べる\n",
    "            diff = float('inf')\n",
    "            for edge in path:\n",
    "                diff = np.min([diff, Gf[edge[0]][edge[1]]['capacity'] - Gf[edge[0]][edge[1]]['flow'] ])\n",
    "            \n",
    "            # path上のedgeのflowを更新\n",
    "            for edge in path:\n",
    "                if edge in forwardEdges:\n",
    "                    Gf[edge[0]][edge[1]]['flow'] += diff\n",
    "                    # このとき、backward edgeのcapacityを更新する必要あり？\n",
    "                    Gf[edge[1]][edge[0]]['capacity'] += diff\n",
    "                else:\n",
    "                    Gf[edge[0]][edge[1]]['flow'] -= diff\n",
    "                    Gf[edge[1]][edge[0]]['capacity'] -= diff\n",
    "    \n",
    "    # もともと無かったedgeを消去\n",
    "    for edge in Gf.edges():\n",
    "        if not edge in forwardEdges:\n",
    "            Gf.remove_edge(edge[0],edge[1])\n",
    "    \n",
    "    return Gf"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "T = fordFulkerson(G, 's', 't')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "code_folding": [
     0
    ],
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAgMAAAFkCAYAAAC9wjgoAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAAPYQAAD2EBqD+naQAAIABJREFUeJzt3Xd8FGXix/HPJguEXqSohygYA0mkSDnBCIIUhcMKKsoJ\nNpoU6fJDQEQiKtKjRkAQj3KoeHoISDs5QBA5OoQOgooggkCCJGST+f3xMGwS04BNNsl8369XXmFn\nZidPdDPznae6LMuyEBEREccK8HcBRERExL8UBkRERBxOYUBERMThFAZEREQcTmFARETE4RQGRERE\nHE5hQERExOEUBkRERBxOYUBERMThFAZEREQcTmFARETE4RQGREREHE5hQERExOEUBkRERBxOYUBE\nRMThFAZEREQcTmFARETE4RQGREREHE5hQERExOEUBkRERBxOYUBERMThFAZEREQcTmFARETE4RQG\nREREHE5hQERExOEUBkRERBxOYUBERMThFAZEREQcTmFARETE4RQGREREHE5hQERExOEUBkRERBxO\nYUBERMThFAZEREQcTmFARETE4RQGREREHE5hQERExOEUBkRERBxOYUBERMThFAZEREQcTmFARETE\n4RQGREREHE5hQERExOEUBkRERBxOYUBERMThFAZEREQcTmFARETE4RQGREREHE5hQERExOEUBkRE\nRBxOYUBERMThFAZEREQcTmFARETE4RQGREREHM7t7wKISP4QFxfHgQMHSEhIoEiRIgQHB1OiRAl/\nF0tEfEBhQEQyFBMTQ3R0NMsXL2bvoUNYlnV5n8vlonq1arRs04bu3bsTFhbmx5KKyLVwWSn/ukVE\ngMOHD/Nit258vXw5Fd1u2nk8NADCgGLAH0AMsBFY4Hbzq8fD/S1b8t4HH1C1alV/Fl1EroLCgIik\nMn36dPr27k15j4c3PB7aA4UzOf4i8Bnwf243p9xuJk6ZwgsvvJA7hRURn1AHQhG5LDIyki5duvBk\nfDw7PB6eIvMgwKX9TwE7PR6ejI+nS5cuREZG5nxhRcRnVDMgIoCpEejSpQuvA8Ou4TyvAyMune/5\n55/3TeFEJEcpDIgIhw8fpmZYGE/GxzPtGs9lAV2BeUFB7IiJUR8CkXxAYUBEaN2qFbu/+YYdHg8l\nfXC+c0BNt5uwZs1YsmyZD84oIjlJYUDE4WJiYggPD2cOpu3fV+YCHS+dPzQ01IdnFhFfUwdCEYeL\njo6mottN+3T2LcBcJNaks++DS/tiMjhvO6Ci283777/vm4KKSI5RGBBxuOWLF9PO40l31MDfgBLA\nJ+ns+wS4HTP3QHqKAO08HlYsWeKbgopIjlEYEHGw2NhY9h46RIMM9gcBD2DmEUjZnngC+C/QIYvz\n1wf2HDxIXFzcNZdVRHKOwoCIgx08eBDLsjJ8ugd4AvgVWJVi26eYcPB4FucPByzL4sCBA9dUThHJ\nWQoDIg6WkJAAmCmGM3I/UAqYn2LbJ0AdIDiL8xdN83NEJG9SGBBxsCJFigBmrYGMFAYeBv4FJAM/\nA9+SdRMBwIU0P0dE8iaFAREHCw4OxuVyZTgiwPYE8BuwEtNEAFk3EQDswqxuGBycVR2CiPiTwoCI\ng3k8Hq4rVYqNWRzXAigL/BPTRPBX4OZsnP9/QI1bb6VEiRLXVlARyVEKAyIOlJyczIwZMwgJCeG3\ns2eZj1l9MCNu4FFMrcD3ZK+JIAGzvHGL1q2vvcAikqMUBkQcZuPGjTRq1Ijnn3+ekydPAnAaM3ww\nM08A5wEX8Fg2fs4C4FePhx49elxLcUUkF2g6YhGHOHnyJEOHDuXDDz8k7Z99AHADsBt8tjZBKBB4\n441s3LyZSpUq+eCsIpJTVDMgUsB5PB6ioqIICQlh+vTpfwoCYEYJ/AL088HPs4D+wOlChTh3/jwh\nISFMmjQJj8fjg7OLSE5QGBApwNasWUO9evXo3bs3Z86cyfTY8Jo1+RAYfQ0/z7r0/g+BqPff5+DB\ng3Ts2JF+/fpxxx13sGrVqms4u4jkFIUBkQLo2LFjdOzYkSZNmrB9+/ZMj61WrRoLFy5k+/btjB49\nmuFAFyD2Cn/mOaArMAKIjIzk+eef57rrruO9997jf//7H6VKlaJZs2Z06NCBn3766ap+LxHJIZaI\nFBgJCQnW22+/bZUoUcLCPKhn+FW0aFHr9ddfty5cuJDqHNOmTbOKBwVZVdxuaw5YCWBZmXzFgzUH\nrCput1U8KMiaPn16umVLTk62Pv74Y6tSpUpWsWLFrDFjxljx8fG58Z9FRLKgDoQiBcSyZcvo06cP\ne/fuzfLY9u3bM27cOKpUqZLu/sOHD/Nit258vXw5Fd1u2nk81MesNVAUM7PgLsw8Agvcbn71eLi/\nZUve++ADqlatmunPPnfuHK+99hqTJ0+matWqTJo0idYafijiVwoDIvncDz/8QP/+/fnXv/6V5bGh\noaFMmTKF5s2bZ+vcMTExREdH89HUqcSms75AaHAwLVq3pkePHoSGhl5RuWNiYujTpw8rV67kwQcf\nZMKECVSrVu2KziEivqEwIJJPXbhwgbfffps333yT+Pj4TI8tWbIkI0eOpHfv3hQqVOiKf1ajRo34\n7rvvUm1r0KAB33///RWfKyXLsliwYAH9+/fn119/ZfDgwQwZMoRixTJbOklEfE0dCEXyGcuy+PLL\nLwkLC2PkyJFZBoFOnTqxd+9e+vfvf1VBICOBgYHXfA6Xy0X79u3ZvXs3gwYN4q233iI0NJTPP/88\n3SGQIpIzFAZE8pG9e/fSunVrHn74YX744YdMj61Tpw5r165l1qxZ3HDDDblTwKtUvHhxXn/9dXbt\n2kWtWrVo164drVq1Yvfu3f4umogjKAyI5ANxcXEMGTKEmjVrsnTp0kyPLVu27OXhfBEREblUQt8I\nDg5m4cKFfPXVVxw+fJhatWoxaNAgzp075++iiRRoCgMieZhlWcybN4/q1avz1ltvkZiYmOGxLpeL\nbt26sW/fPnr06OGTanx/+dvf/sbOnTt57bXXeO+996hevTqzZ89W04FIDlEYEMmjtm/fTtOmTXnq\nqac4duxYpsc2bNiQjRs3Eh0dTfny5XOphDkrKCiIoUOHsmfPHpo0acLTTz9NkyZN2Lp1q7+LJlLg\nKAyI5DFnzpyhT58+3HHHHaxevTrTYytWrMhHH33Et99+S7169XKphLnrpptuYv78+axcuZLTp09T\nr149evbsyenTp/1dNJECQ2FAJI9ITk5mxowZhISEMGXKFJKTkzM8NjAwkH79+rFv3z46d+5MQEDB\n/1O+99572bp1K+PGjWP27NmEhIQwbdo0kpKS/F00kXyv4F9BRPKBjRs30qhRI55//nlOnjyZ6bHN\nmjVj27ZtjB8/ntKlS+dSCfOGQoUK0bdvX/bu3Uvbtm3p2rUrd95555/mQBCRK6MwIOJHJ0+epEuX\nLtx5551ZTuBTuXLly9Xl4eHhuVTCvOn666/no48+Yt26dViWRaNGjXjuuec4ceKEv4smki8pDIj4\nycaNGwkJCWH69OmZ9pIvXLjw5Y50jz/+OC6XKxdLmbc1atSI77//nujoaL788ktCQkKYNGkSHo/H\n30UTyVcUBkT8pGbNmpQrVy7TY9q0acOuXbuIjIykePHiuVSy/CUwMPDykMqOHTvSr18/7rjjDlat\nWuXvoonkGwoDIn5y/vx5QkJC0t1XrVo1Fi5cyKJFiwgODs7lkuVP11133eXJlkqVKkWzZs3o0KED\nP/30k7+LJpLnKQyI5LKkpCSio6MJCQlh3bp1qVb7K1q06OVpedu2bevHUuZfdevWZe3atXz88ces\nWrWK6tWr8+abb5KQzqqLImIoDIjkonXr1tGgQQN69OjBww8/zP79+/nyyy8pXLgw7dq1Y/fu3Qwb\nNoygoCB/FzVfc7lcPP300+zbt4/u3bszfPhwatasyZIlS/xdNJE8SWFAJBccP36czp07ExERQWBg\nIN999x0ffvghFStW5LbbbmPPnj189tln3Hzzzf4uaoFSqlQpxo0bx7Zt26hSpQpt2rThoYce4tCh\nQ/4umkieojAgkoMSExOZMGECISEhLFq0iGnTprFhwwbuvPPOVMdVrVrVTyV0hrCwMJYvX86nn37K\nli1bGDZsmL+LJJKnuP1dAJGCauXKlfTp04c9e/bQo0cPRo0aleXoAck5LpeL9u3b07p1a06fPo3H\n48Ht1iVQBFQzIOJzR48e5fHHH6dFixaUK1eOzZs3ExUVpSCQRxQvXpybbrop6yDw8cdw5kzuFErE\nzxQGRHwkPj6eyMhIQkNDWbt2LbNnz2b16tXUrl3b30WTK3H8OAwdCv/3f3D0aOp9WkJZCijVkYn4\nwL59+2jTpg1HjhyhX79+DB8+nJIlS/q7WHKl4uOha1dz0//3v6FWLbPdssDlMl8AycnggMWhxDkU\nBkR8oHz58tSoUYOvvvqKGjVq+Ls4cjXOnYOxY2HzZvjuO6hc2bvviy9gxw5o3RoaNFAQkAJHn2iR\nrJw96207zmBZ4bJly7Jw4UIFgfxswQJYtQoGDjRBwF4aOTkZ/vtfExIaN4Z77oEsVpYUyW9UMyCS\nll0lDKbNuGdPCAqCOXOgcOF036LFg/K5hAT47DOoUgWeespss5/+AwJg4kTYtMm8/uUXqFAh43Ol\n/PyI5BOqGRBJK+WFvEoVmDXLdCrr0gW2bDHbM6ghkHzqv/+F3383T/0VK5ptKfsHgPkMHD5sPgfg\nrTlIy36fOhtKPqIwIJLW6dPw1luweLF5Xa4cvP8+/PEHDB5stqnNuGD5+Wdz846IMK9T3sgDAkx/\nguXLwe321hykDI3ffQfjx0PnzqapIe1+kTxOVzRxroye7s+ehe3bzcXfdvvtMGAA7NplOplJwWDf\n9E+cMCMJwsPN67RP93anwgcfhGLFwOMxISEpCf71L1Oj8MUXcPEitGsHw4aZY0TyCYUBca6AALhw\nAf75T/j+e+/Fu2pVuPde+Okn2LDBe3zDhtC7N7zzDvz2m3/KLL5l3/Q3bYIWLcy/U1b/u1yQmGia\nEWJj4bnnzHY7JCxdaj4PTz4Jq1fDvHkwdaqZsOiXX9L/mcnJakKQPEdhQJwpORnGjIHy5SEyEtq2\nhRdegG3bzP7atc1NYevW1O/r1s08/f373+a1Lur5n2WZ+QQuXjT/Dgw02xMTzfedO82NvkkTuOkm\n87koVMjsmzULypaFIUO856tWDYoU+fNn5/x5EyIDAtSEIHmOwoA40/79ZijZu++aToHvvQdHjkCv\nXmZ//fowebK5+adUrhw8/DDMnp37ZZac4XLBddelnlTot99MOJwzxzQXnTgBzz9v9tnNS6tWwYED\npokg5ZDSQoXM0EN7GeoLF0zT0gMPQM2aptYpbVAQ8TOFAXGmjRth7154+mnTKax9e/N0t22bqeoF\n76QzaZ/+IyJMv4KTJ/WEV1C0auUNfklJUKoU3HCDGTkwZIi5od92m9lv1wps3Gj6DzRtal7bIeGb\nb8z3li3N92HDTBi46y745BNTuzBkiJqaJE9RGJCC40qq7M+dMxf3Y8e82xo3hkcfhTfeSH2+tDf8\noCBTQ6AmgoIjOBhCQ82/AwPNfBJvvmlGkMycabaVLWuaBWznz5t+BA0amNculwkN0dHQoYPZNncu\nrFhhJjIaPdp8xoYPh5UrTadEkTxCYUDyv7Q37cx6cdvHXned+XfK6tpixUxNwb59pobA5Uo94sB+\nb9265n1lyvjud5C8xbK8n6POnc1n4l//gjvu8B4TG/vnuQZmzTLHDhhgXn/wAYSFwRNPeI8pXBjq\n1YMffsjRX0HkSigMSP5nhwB76Ne775rOYJkd+8AD5inu228hLs67/+aboU4dWLbMvE45n4D93rNn\nTRXwqVO+/T0k73C5TPMReEPBQw95Fy4CeOYZExo++sh8FoYPh0mTzIiT224znQ5//hnuu898rmy/\n/mqCQPny5nV2J7BSTZTkIIUByX/SXhTPnzcTvjz3nLkAz5plOnxlJCnJ1AI8+qhp312zxruvdGkz\npLBKlYx/bpky8Nhjpk1ZCj53BrO2h4WZWoOXXjL9SGbPNgFh9Giz/7vvoFIl02nQlpQE//mPCaKP\nPmq2ZXcCK/VPkRykMCD5jz32+8gR8/rCBXOj7tMH1q0zVfhr1mT8JGVfVHv1gpIlzWyD9rr1O3ea\noHDrrRm/LzQUHnnEt7+T5D+BgTBokKkpmj7dBNGXXzafHzD9So4fN00CtkOHzLH2yISMpjS22fvn\nzTOTGqVkWaotEJ9RGJD85/ffoW9feP1187p8eejY0fT8DguDNm3MBTe9anzL8j6J3XgjjBplZp5r\n2tQM+frb37xDwEQyk7Jfwd13e2uT7Bt0yZJmASS7b8C5czBtmpnu+tVXzTZ7ToOM2PunTzdB99w5\n8zohIfVQSK2VIddIYUDyn7JlzbSxcXHehYOuv957k3/1VTMGPL3e2ilXIwQz3GvhQpgyxfT03rjR\nNDkUKZLjv4bkcyn7FaTdDtC6tZl/4MknzQiDFi3MjIUjR5rmqOzWCixcaIYztm1rhjzu3g39+5uh\nkKtXm2O0VoZcI32CJH+xn7ruucd8nzvXu8/lMvsbNDAdvWbNMj2+U4qPN+O+O3f2zjBXoYKpEXjt\nNRMykpP1pCXXrlQp+PxzEzhnzTKjUKZOhR49zH57bYOM2LUCn3xi5ryoXt28PnjQDHl0uUxz1X33\nmREMItfAZVlqdJJ86t134S9/MTMC2jwe87T22WfQqZOZU94eB56cbC7Ao0ebuegnTfpzR0H7GEnX\n5s2bqVevHps2baJu3br+Lk7elvazlJSUdbNAev74w4xKsCc9Au/n/ORJU/Nw992mxkHkKumqJ/5z\ntU/fdn7t2TN1EABvtW379qYD1/z5sGgRvPgiLFli9vXvb8aMpzdiQEFAfCUgwHxW7af/wEDvZzc2\nFv7+dzMsMTOWZTok2kHA7jRof84rVDBBYP58M2RR5Crpyif+Y9947fb77FZSpRxild577G133WXa\n/x94wHQmtJ9k7d7eWbXZilwrlyt1bYDLZZ7qp083owPKls36/Wlf26NpwHSmPXPG/LtixeyVSZ97\nSYfCgPjP4sVmQaB69eDHH71t/lcivbHX27ebC+PixWbEwe+/myentPMCXE2Vrci12r/fDDGcPdtM\nZJTdz3zK4woVMmtrdO5sar5GjTLbM7vRnz1rvtufe7UQSwoZzKYh4mNbtpgFWuxZ12bOND2sb7jB\nNBd89JGZwc2yrn1ylbJlzeiAlFPAJiWZ86oZQPwtNNR8Pq+Uy2UWN1q61HSc3bYNbr8dPvzQLK8M\nqQOu3UfhxAn4xz/MeggHDpgpt//v/7wLLomgmgHJLc88k3rSlBo1zAxs48ebkQFffGE6StntrNei\nShVvEPB4vGvUKwhIXpSd8LtnD/TrB82amaGzYWEmFCxZ4g0CadnBoGtXM4qhTh0YMcIsy5xRZ0PV\nFjiWagYk5508aVaFSzk/e6NG5gvMBe4//zHVpl27mpqCtFX4V1tjkNFUsiL5xZkz5kn+yy/NCJlp\n07xP9VmNUJg61cxFMHeumfcATCju1w+6dze1dWBqHMqX15THDqZHJcl5FSqYedrt9kx7FIH9FNKg\ngVkNbt488zq9i5suUuJUZcqYeQpGjDBDZuvUMashJiamH5rtvyuPB8aMMWt2NG/uPebWW82+lP0L\n2rUzzQ0JCeb1p5+avjbiGAoDkrPsC1OtWt6VAG32Df6GG0ztwPHjZrY1+POww1mz/jw3u4gTWJaZ\nwGjkSDPrZteu5t9lypiROPbfSmxs6imKly6FX34x6yAULuw934YNEBLiXcxryRJT01C5spl5MykJ\nJkwwtXXiGAoDkrNcLjPr3223mTna7X4BNjssRESYfgQzZ5rXiYlmASLbiBFmJjbQ7IDiLPYoG3sd\nhJdeMjf5FSvMpFsBAWbNgubNTVOCfdzMmWa9jZTNc6dOmdE2JUp4F1B67z0T1u+4w7wODDRzF6xd\nm3u/o/idwoDkvKAgc0E6eRLWrzfb7Bu6/RQTHGzmbt+920wLXLMmvPGG9xwvvuit1lRHQHGalOsg\n2Df7Ro28zQQbNpgFkBITzXHx8WZfcDAUL+49z+rVZlXP1q3NcWfPmhAeEZF6noLly739CdSp0BHU\nu0pyR+vWsGCBqbps3vzPN/QzZ2DHDjN2OioKHn8cBg707r/5Zrjzztwts0helF6n2JYtzd+PfeMO\nCjKrctoLGYEJETNnmpk5O3c220qXhrFjU/cfOHrUHFO6tHmt/jqOoDAguSMszDz5r1wJX31lVmBL\nOQ76b38zfQY++MAsRWyz53fv0MF/ZRfJ65KSoGjR1Nvat4evv4bBg6F2bZg8Gc6fN2tzlC/v7WwY\nEJC6I+L+/aZvQtrzSYGmMCC557nnzBCm/v1NTYF9AapUyXQQDA/3HuvxaG4AkexKbwRORIQJAK++\najrv1qoFgwaZJjhb2r+vxEQzQdiJE96hiOIICgOSe265Bd5+26wZ0KsXPPss/PWv5qnGDgL2amya\nH0Dk2rVsab7OnDGjD1JKu8aHywUxMfDvf5uOh1mtmyAFih67JEelWiHbskwv5vnzTaem114z1ZEp\nn2oUAkR8JynJ/N2lDQIp2UHA4zETf507By+/nHtllDxBYUByhGVZbN++PXUYsJ9EQkPhnXdMc4G9\n+pqI+F5gYNYdAO39778Pq1aZPjvVq+d40SRvURgQn4uJiaFFixbcc889eOxhUCnZAaF5c1VF5jNV\nqlRh6tSpVKlSxd9FEV+xLDPj4KuvmiG8zz7r7xKJHygMiM+cPXuW/v37U7t2bX788Ufmzp1L4ZQz\nn9k0VCnfKleuHM888wzlypXzd1HEV774wkzoNWqUCQLFivm7ROIHLsvSjBJybZKTk5k9ezaDBw8m\nNjaW4cOH069fP4oUKeLvoolIVrZtM0MN//IX89oXy4hLvqMwINdk8+bN9OrVi/Xr19OhQwfGjh1L\n5cqV/V0sEfEBy7JwKRg4gpoJ5KqcOnWKHj16UL9+fWJjY/nmm2+YN2+egoBIAeLxeOjWrRs//fST\nv4siOUxhQK5IUlIS0dHRhISEMHfuXCZOnMiWLVto2rSpv4smIj5kWRY//PADX375JdWrV+fNN98k\nwV7iWAochQHJtnXr1tGgQQN69OjBQw89xL59++jTpw9uzQ0gUuC4XC5uu+029u7dS/fu3Rk2bBg1\na9ZkyZIll4+ZM2cOn3zyCWptzv8UBiRLx48fp3PnzkRERBAQEMD69euZMWMGlSpV8nfRJDckJsKP\nP5pFpE6f9ndpJJeVLl2acePGsW3bNm666SbatGnDQw89xP/+9z969+7NE088QfPmzdm1a5e/iyrX\nQB0IJUOJiYlERUXx6quvUrhwYcaMGcNzzz1HYHrzoEvBEhtrZqP75z/h++/h4kVvL/PKlaFVK+ja\nFRo08HdJJRdZlsWCBQvo378/P//8M8n2UuRAYGAgvXv3ZuTIkZS2VzyUfENhQNK1cuVK+vTpw549\ne+jRowejRo3S2HKnGD8eIiPh1lvhgQfM+hE33mhWsTt9GnbuhDVrzPj0O++EKVPgttv8XWrJRWvW\nrKFJkybp7qtYsSJvv/02Tz/9NAFaaCzfUBiQVI4ePcrAgQP59NNPiYiIICoqijp16vi7WJKbnnwS\nhg1LvYpkehISYOZMKFzYrEgpjpCcnMxdd93Fhg0bMj2uYcOGREVFUa9evVwqmVwLhQEBID4+nnHj\nxvHGG29QqlQpxo4dS8eOHTXGWERSsSyLTz75hAEDBvDzzz9neqzL5aJr165ERkZy3XXX5VIJ5Woo\nDAiLFi3ipZde4siRI/Tt25fhw4dTqlQpfxdLRPKwuLg4IiMjGTduHIlZLDhWtmxZIiMj6dq1q/oc\n5VEKAw524MAB+vbty6JFi2jRogWTJ08mNDTU38WSvCBttf+MGf4ph+R5+/bt46WXXuLrr7/O8tg6\ndeoQFRVFRERELpRMroR6dzjQ+fPnGTZsGOHh4ezYsYMFCxawbNkyBQHxuvnm1F8iGQgJCWHx4sV8\n+eWXVK1aNdNjt27dyt13302nTp345ZdfcqmEkh2qGXAQy7L47LPPGDBgAL/++isvv/wyL7/8MsW0\nSpmI+MCFCxcYO3YsY8aMIT4+PtNjS5YsyauvvkqfPn0oVKhQLpVQMqIw4BAxMTH07t2b//znPzz4\n4INMmDCBatWq+btYkl/Y09BqJUrJhh9++IEBAwbw+eefZ3lsaGgokydPpkWLFrlQMsmImgkKuLNn\nz9K/f39q167Njz/+eLk6T0FAsrR8ObRpA2XLmjXuixUz/27TBlas8HfpJA+75ZZbWLBgAUuXLqV6\n9eqZHrt7925atmxJ+/btOXLkSC6VUNJSzUABlZyczOzZsxk8eDCxsbEMHz6cfv36UURPdpIds2bB\nCy9A+/Zw331gTz194gQsWwaffQYffghPP+3fckqed/HiRSZPnsxrr71GXFxcpscWLVqUoUOHMnDg\nQIKCgnKphAIKAwXS5s2b6dWrF+vXr6dDhw6MHTtWSwvLlQkJgZdegp4909//3nswYQLs35+75ZJ8\n69ixYwwePJg5c+ZkeWy1atWYOHEibdu21VwnuUTNBAXIqVOn6NGjB/Xr1yc2NpZvvvmGefPmKQjI\nlTt6FDJrw23eHLTGvVyBG2+8kdmzZ7N69Wpq1aqV6bGHDh3iwQcfpG3btuxX4MwVCgO5LC4ujq1b\nt7Jhwwa2bt2aZbVZdiQlJREdHU1ISAhz585l4sSJbNmyhaZNm157gcWZwsNNM0BGZsyAsLDcK48U\nGI0bN2bTpk1ERUVRpkyZTI9dvHgxt99+O0OHDuX8+fNX9fNy4ppbEKmZIBfExMQQHR3N8sWL2Xvo\nUKq1v10uF9WrVaNlmzZ0796dsCu8wK5bt45evXqxZcsWnn32WcaMGaOlheXarVoFbdtCtWqmhiBl\nn4GVK+HQIVi0CDJYrEYkO06ePMkrr7zC9OnTyepWVLlyZd555x0ef/zxLJsOcvKaW2BZkmMOHTpk\n3d+ypQUuYUVXAAAgAElEQVRYFd1uqwdYM8D6Dqztl77PAKvHpf2AdX/LltahQ4eyPPcvv/xiderU\nyQKsevXqWevXr8+F30gc5fBhyxo82LKaNLGskBDz1aSJZb38stkn4iPff/+99de//tUCsvxq2rSp\ntWPHjnTPk5PX3IJOYSCHTJs2zSoeFGTd7HZbc8BKMKvBZ/iVANYcsKq43VbxoCBr2rRp6Z734sWL\n1vjx462SJUta1113nTV16lTL4/Hk8m8nIuJbSUlJ1owZM6wKFSpkGQgCAwOtvn37WmfOnLn8/py6\n5jqFwkAOGD16tAVYL4B1LosPZNqvc5feB1ijR49Odd4VK1ZYYWFhVkBAgNWzZ0/r1KlTfvoNRURy\nxu+//2716dPHCgwMzDIUVKxY0Zo5c6b1+uuv58g110kUBnxs2rRpFmC9foUfyLRfoy59OKdPn24d\nOXLEeuyxxyzAioiIsLZs2eLvX1OcrlMny2rWzN+lkAJs+/bt1j333JOtpgNfX3OdSB0Ifejw4cPU\nDAvjyfh4pl3juSygCzDb7cbldlOmTBnGjh1Lx44dNe5W/G/oUPjlF5g5098lkQLMsizmz5/PgAED\nOHbsWLrHBADPAtMzOMd6YBnQD8hsYXYL6ArMCwpiR0xMlosuFTQKAz7UulUrdn/zDTs8Hkr64Hzn\ngFAg6Oab2bJ9O6VKZfZRFhEpmOLi4oiMjGTcuHEkJiZe3h4A3ADshgyvueOAwcBhoEoWP+ccUNPt\nJqxZM5YsW3btBc9HNM+Aj8TExPD18uW84aMgACbFjgUOHTnCzz//7KOziojkLyVKlGDMmDHs3LmT\n+++///L2ZOBtMg4CYJ74s6sUMMbj4evly9m9e/fVFTafUhjwkejoaCq63bTP4rg4oC9QFQgCKgGt\ngK0ZHN8OqOh28/777/usrCLX7Mcf4bnn/F0KcZiQkJDLi62VKlWKcpDpNfc1TK0AwC2YG14gcDST\n9zj1mqsw4CPLFy+mncdD4SyO6wZ8ADwGvA8MAophqrnSUwRo5/GwYskSn5VV5JqdPm0WMxLJZS6X\niwcffJAbypfnCcj0mtsOePLSvycBs4F/ABUyeY9Tr7lufxegIIiNjWXvoUOXE2hmFmM6Br6dYtvA\nLN5TH4g+eJC4uDhKlChxtcUUyb5//zvz/YcO5U45RNIRGxvLvsOHeTmL424H6gL/BB4i6z4DNide\ncxUGfODgwYNYlkV2JrUsA2wAfsF0fMmOcEyv2gMHDlCnTp2rLaZI9j38MLhcZtBVRjSqRfzkSq65\nV8OJ11w1E/hAQkICYKr7s/I2sBO4CbgT06Z1OIv3FE3zc0Ry3A03wOefQ3Jy+l+bN/u7hOJgV3LN\nvRpOvOYqDPhAkSJFAPgjG8c+BhwCooC/AO9gUujSTN5zIc3PEclx9erBpk0Z78+q1kAkB13JNfdq\nOPGaqzDgA8HBwbhcLmKyeXwloDvwOaZW4DogMpPjd2E6zQQHB19bQUWya9AguOuujPcHB8M33+Re\neURSuJJr7tU0Zjnxmqsw4AMlSpSgerVqbMziuGTMpBYplQduBDKrjPofUOPWWx3TkUXygMaNIcV4\n7j8pXhzuuSf3yiOSQokSJQi++eYsr7kAxS99P3MF53fiNVdhwEdatmnDArebi5kcE4tpGngWmIiZ\nPvMJzAfvqQzekwAscLtp0bq1L4srIpIveTweoqKiOHLsGPMh02suQD3MxENDMUML5+NtBkiPU6+5\nmo7YR2JiYggPD2cOGd/YE4HhmHmyD2FqCoIxTQZdM3jPXKDjpfOHhob6ttAiGXn22dSjBWbM8F9Z\nRC5Zs2YNvXr1Yvv27Ze3ZXbNtb0BRGNGcSWT+dTETr3mKgz4UE6tTUClSmz43/+oXLmyD84qkg2v\nvZb69auv+qccIsCxY8cYNGgQc+fOTbU9O2sTXAknr02gMOBDObFq4ZxChShRujR//PEHw4cPp1+/\nfo7q4SoiznXx4kUmTZrEqFGjiIuLS/eYrFYtzC6nr1qoPgM+VLVqVSZOmcJ0YPQ1nMe69P4Pgaj3\n3+fAgQN0796dYcOGUbNmTZY4bJpMEXGeZcuWUatWLQYPHpxhEABT7f8hvrnmTgcmRUU5LggAYInP\njR492gKsF8A6Z0ZjZ/vr7KX3AVZkZGSq8+7cudO69957LcB68MEHrYMHD/rpNxQRyRmHDx+2Hnnk\nEYtL18HMvkJDQ60VK1bk2DXXSRQGcsi0adOs4kFBVhW325oDVkIWH8h4sOaAVcXttooHBVnTp09P\n97zJycnWp59+at10001WkSJFrOHDh1vnz5/P5d9ORMS3/vjjD2vkyJFWUFBQliGgZMmS1rhx46yL\nFy9efn9OXXOdQmEgBx06dMi6v2VLC7Aqut1WD7A+BOs7sLZd+v4hWD0u7Qes+1u2tA4dOpTluePi\n4qxXXnnFKly4sFWlShVrwYIFVnJyci78ViIivpOcnGx98cUX1i233JKt2oBOnTpZx44dS/dcOXnN\nLegUBnLBrl27rN69e1uhwcGWy+VK9cF2uVxWaHCw1bt3bysmJuaKz71//36rbdu2FmC1aNHiqs4h\nIuIPe/bsse67775shYA6depYa9euzdZ5c/KaW1BpNEEui4uL48CBAyQkJFCkSBGCg4N9MsvVV199\nRd++fTly5Ah9+/Zl+PDhlCpVygclFsnAxx9DRATcequ/SyL5TFxcHKNHj2b8+PEkJiZmemzZsmWJ\njIyka9euBAYGXtXPyolrbkGjMFCAxMfHM378eEaPHk3p0qUZO3YsHTt2xKWlZiUnBARAoULQtStM\nmeLv0kg+YFkW//znPxk4cCDHjh3L9FiXy0XXrl0ZPXo05cuXz6USOpeGFhYgQUFBDB06lD179tC4\ncWOefvppmjRpwtatW/1dNCmIkpNhzx5w0CxtcvW2b99O06ZNeeqpp7IMAg0bNmTjxo1ER0crCOQS\nhYECqEqVKnzyySesXLmS06dPU69ePXr27Mnp06f9XTQpaKpWhRdf9HcpJA87c+YMffr04Y477mD1\n6tWZHluxYkU++ugjvv32W+rVq5dLJRRQGCjQ7r33XrZu3co777zDP/7xD0JCQpg2bRpJSUn+Lprk\ndx4PHD3q71JIHpacnMyMGTMICQlhypQpJCcnZ3hsYGAg/fr1Y9++fXTu3JmAAN2acpv6DDjE8ePH\nGTJkCLNmzaJevXpERUXRsGFDfxdL8qtt26BuXVCwlHRs3LiRXr168f3332d5bLNmzZgyZQrh4eG5\nUDLJiOKXQ1x//fWXq9+Sk5Np1KgRzz33HCdOnPB30USkgDh58iRdunThzjvvzDIIVK5cmfnz57Ny\n5UoFgTxANQMOlJSUxPTp0xk6dCgej4dRo0bRs2dP3G63v4smeUXdupnvv3AB9u1TzYAA4PF4iI6O\nZvjw4Zw5cybTYwsXLszAgQMZOnQoxYsXz6USSlYUBhzs1KlTDBs2jA8++IDw8HCmTJlC06ZN/V0s\nyQuCgqBDB9NBMD2//ALTpikMCGvWrKFXr15s3749y2PbtGnDpEmTCA4OzoWSyZVQGBA2b95Mr169\nWL9+PU888QTvvPMOlStX9nexxJ/q14fnn4cePdLfv3Ur1KunMOBgx44dY9CgQcydOzfLY6tVq8ak\nSZNo27ZtLpRMrob6DAh169Zl7dq1zJo1i1WrVlG9enXefPNNEhIS/F008ZeICNi7N+P9JUtCkya5\nVx7JM5KTkxk7dizVq1fPMggULVqU119/nV27dikI5HGqGZBUzp49y6hRo5g0adLlNN+6dWt/F0tE\n8gjLsmjdujVLly7N9Lj27dszbtw4qlSpkkslk2uhmgFJpXTp0owbN45t27Zx00030aZNGx566CEO\nHTrk76KJSB7gcrkYNmxYhnMBhIaGsmLFCj799FMFgXxEYUDSFR4efvkPesuWLYSFhTFixAj++OMP\nfxdNctqVTib08885Uw7JcxITE5kwYQJt2rShcOHCqfaVLFny8oNE8+bN/VRCuVoKA5Ihl8tF+/bt\n2b17NwMHDuStt94iNDSUzz//HLUuFWANGkC3brBxY8bHnD1rRhPcfjssWJB7ZRO/WblyJXXq1GHg\nwIF06tSJvXv3cuONNwJcft2/f38KFSrk55LK1VCfAcm2AwcO0K9fP7766itatGjB5MmTCdUiNQXP\nqVMQGQkzZpghhvXqwY03mn///jvExMCuXWYuguHDoU0bf5dYctDRo0cZOHAgn376KREREURFRVGn\nTh0Avv76a0qWLElERISfSynXSmFArthXX31F3759OXLkCCtXrqRx48ZaJrkgunABFi2CtWvhyBHz\nunx5uOMOuO8+UysgBVZ8fDzjxo3jjTfeoFSpUloSvYBTGJCrEh8fz7vvvkv37t01i5hIAbNo0SJe\neukljhw5Qt++fRk+fDilSpXyd7EkBykMyDWxLEtPCiIFxIEDB+jbty+LFi1SU6DDqAOhXJMsg8DH\nH0MWc5WLiH+dP3+eYcOGER4ezo4dO1iwYAHLli1TEHAQrUwjOeP4cZg8GWbNgjp1oEwZ7z7LAtUm\n5EvJycl4PB7cbrfWnC8ALMvis88+Y8CAAfz6668MGTKEl19+mWLFivm7aJLL1EwgvhcfD48/bm76\nI0ea3ujw5xCQnAy6oeQrx44dIzo6mu7du18eVib5W61atahatSoTJkygWrVq/i6O+InCgPjWuXMw\ndizMnAnffQcpFzz6179gxw5o3dqMZZd8Z/PmzdSrV49NmzZRN6tljsX/zp41IbxMmXTDt8fj4fjx\n41qYTNRnQHxswQJYtQoGDjRBwF7VLjkZ/vtf2LwZGjeGe+6Bkyf9WlSRAifls93Ro/D3v0OXLnDx\nYrq1cG63W0FAAIUB8aWEBPjsM6hSBZ56ymyzL0ABATBxopmk5v77TVNChQoZn0sVViJXLmUzXJUq\nps/O8eMmEGzZYrYnJ/unbJKnKQyI7/z3v2aGunvugYoVzTb74mRfgI4fh8OHzcUJvDUHadnvUygQ\nyb7Tp+Gtt2DxYvO6XDl4/3344w8YPNhsUz8dSYc+FeI7P/9sbt721KQpb+QBAaY/wfLl4HZ7aw5S\nPsl89x2MHw+dO5umhrT7RcTI6On+7FnYvt38ndluvx0GDDBTSI8dmzvlk3xHYUCunX3TP3HCVP+H\nh5vXaZ/uN282N/wHH4RixcDjMSEhKcl0LrznHvjiC9O+2a4dDBtmjhGR1AICzPTQ//wnfP+99++k\nalW491746SfYsMF7fMOG0Ls3vPMO/Pabf8oseZrCgFw7+6a/aRO0aGH+nbL63+WCxETTjBAbC889\nZ7bbIWHpUnORevJJWL0a5s2DqVPNhEW//JL+z0xOVhOCOFNyMowZY9aJiIyEtm3hhRdg2zazv3Zt\n8/e3dWvq93XrZoL2v/9tXuvvR1JQGBDfsCyoVctcbCwLAgPN9sRE833nTnOjb9IEbrrJXKzspU5n\nzYKyZWHIEO/5qlWDIkX+fEE7f9482QQEqAlBnGn/fjNq5913TafA994zC0n16mX2169vJvzq1i31\n+8qVg4cfhtmzc7/MkucpDIhvuFxw3XXmu32T/u0388QyZ45pwzxxAp5/3uyz2zxXrYIDB0wTQY0a\n3vMVKmSGHgYFmdcXLpj2zgcegJo1TVVo2qAg4gQbN8LevfD006b/Tfv2Jkhv22Zq1cA7v0fap/+I\nCNOv4ORJhWlJRWFAfKdVK+/TSFISlCoFN9xgRg4MGWJu6LfdZvbbtQIbN5r+A02bmtd2SPjmG/O9\nZUvzfdgwEwbuugs++cTULgwZovZPKRiupMr+3Dnzd3TsmHdb48bw6KPwxhupz5f2hh8UZGoI1EQg\naSgMiO8EB4O9sElgIBQuDG++aYY1zZxptpUta5oFbOfPm34E9oyELpcJDdHR0KGD2TZ3LqxYYSYy\nGj3aXPiGD4eVK02nRJH8Ku1NO7MOs/ax111n/p2yZqxYMVNTsG+fqSFwuVKPOLDfW7eueV/KtUJE\nUBiQnGRZ3otb587mQvWvf8Edd3iPiY3981wDs2aZYwcMMK8/+ADCwuCJJ7zHFC5s1jz44Ycc/RVE\ncpQdAuxRNu++a/rdZHbsAw+YwPzttxAX591/881mUbBly8zrlPMJ2O89e9bUtp065dvfQ/I9hQHJ\nOS6XadMEbyh46CHT0dD2zDMmNHz0kblADR8OkyaZYVC33WY6Hf78M9x3n7nY2X791QSB8uXN6+zO\nqqbqUfGntJ+/8+fN3BrPPWc+67Nmmb41GUlKMrUAjz5qmtLWrPHuK13aDCmsUiXjn1umDDz2mGm+\nE0lBYUByhzuD1bLDwkytwUsvmc5Ns2ebgDB6tNn/3XdQqZLpNGhLSoL//Mc8HT36qNmW3VnV1GlK\n/MkeZnvkiHl94YK5UffpA+vWmSr8NWsyDq3257dXLyhZ0sw2ePSo2bZzpwkKt96a8ftCQ+GRR3z7\nO0mBkMEVWiSXBAbCoEHma+1a81ST8smmXDkzhbG9DDLAoUMwfbp3ZEJSkncoY3rs/fPmQdGiZniV\nLaOOViI54fffTWfYhATzGS5fHjp2NOt0BAZCmzZme6tW3lovm2V5Q++NN8KoUdC/v+l8e8stJjh3\n7546OItkk2oGxL9S9iu4+25vELBv0iVLmgun3Tfg3DmYNs3Mwf7qq2ZbZkEg5f7p083T17lz5nVC\nQuqhkFrARXJa2bJmhs64OO/CQddf773Jv/qqGW6bXsdY+3Nq1wTcdRcsXAhTpphOtRs3miaHIkVy\n/NeQgkdhQPwrZb+CtNsBWrc28w88+aQZYdCihZmxcORI00aa0UJHNnv/woVmOGPbtmbI4+7d5qmq\nWzfTVgtawEVylh1w77nHfJ8717vP5TL7GzQwfWpmzTKda1OKjze1Cp07eyfzqlAB/vY3eO01EzKS\nkxVq5aro6id5W6lS8Pnn5ilo1iwzNGrqVOjRw+y31zbIiF0r8MknZiKW6tXN64MHzZBHl8u0od53\nnxnBIJJT7IAbHm6e5O0FvWz253jYMDPqZs8e777kZDNHQFCQ6QSY3jTdycnm70GhVq6Cy7LUvVry\nMPsCZ8uqf0BG/vjDjEqwJz0C0zzhdpvZ2J580jRTjBx5zUUuyDZv3ky9evXYtGkTdevW9Xdx/Cft\n5zK7LCt7/VMqVzbzbDRrBosWmaf/v/3NfI6LFbvynyuSBUVIydsCAswF1H5qCgz0VrfGxsLf/26G\nJWbGsswF1A4ClmW+7OaJChVMEJg/3wxZFMmKHQTs9vvsPlOlDALpvcfedtddpv3/gQfMkFs7eNlB\nIKvmMZErpDAgeZ/Llbo2wOUyT/XTp5slj8uWzfr9aV/bQ7zA9PA+c8b8u2LF7JVJF2NnW7zYLAhU\nrx78+KO3zf9KpFdDsH27+QwuXgyvv24+m/Pn/3legKupHRPJhMKA5E/795shhrNnm4mMsnshTnlc\noUJmwZfOnU1V7KhRZntmN/qzZ813+2KsVraCb8uW1GtgzJxpOuzdcINZI8OumfLFZ6FsWTM6IC4O\nXnnF20lWnQIlhykMSP4UGmouminnDMgOl8tc2OfMMW2wzZub6V8//NDMzAapn7rsYHDiBLzzjmnH\nve02ExwSEzU/gRM884ypgbLVqGEmuxo/3owM+OIL05ZvN2ldiypVvNNuezze5cDVKVBymCYdkoIh\nOzflPXvMOgcrVpiZ3x55BN5+28yCmNH77WDQtasZjtiuHTz1lJkhMSEBIiP//J7sdhKTvO/kSbMA\nV8qpsBs1Ml9gOvj95z+mhqprV/MEn7YK/2o/DxnN2imSA/RpE2c4cwb+7//gyy+hUyczcZG9jHJW\nIxSmTjVzEcyda+Y9APOk1q+fmfHtppvMtt9+M7PGKQgUHBUqmJn9unQxr+1RBPYNvkEDs/DWvHkm\nDKT3OdLnQfIB1T2JM5QpY+YpGDECPvvMrO72wQemqj+9Jzm7utfjgTFjzEIyzZt7j7n1VrMvZf+C\ndu1Mc0NCgnn96aemA5jkT/ZnoFYt70qANvsGf8MNpnbg+HEzsRX8uX1/1qzUzQwieZDCgDiDZZkJ\njEaONJ2zunY1/y5TxgwPsy/gsbGppyheutRM8PL882bZZNuGDRAS4l1hbskSU9NQubKZDjYpCSZM\nMFXIkj+5XGbWv9tuM9Nh2/0CbHZYiIgw/QhmzjSvExNNM5RtxAgz6RWoI6DkWQoD4gz20C97HYSX\nXjI3+RUr4C9/MRf5c+fM0/+XX3qPmzkT7r03dZvxqVNmCFiJEt4FlN57zzxB3nGHeR0YaOYuWLs2\n935H8b2gIPP//uRJWL/ebLNv6HZgDA4202Tv3m1GGdSsCW+84T3Hiy96a5DUEVDyKH0yxTlSroNg\n3+wbNfI2E2zYYBZASkw0x8XHm33BwVC8uPc8q1ebpWZbtzbHnT1rngwjIlLPU7B8ubc/gYYg5l+t\nW5ub+dKl5nXaG/qZM7BjhxmmGhUFLVvCwIHe/Tff7J0+WySPUgdCcab0emq3bGku6vaNOyjILBVr\nL2QEJkTMnGmWVu7c2WwrXRrGjk3df+DoUXNM6dLmtTqR5V9hYebJf+VK+Oors9iV3en0xAkzRPX4\ncdMHxe5oCN7Ohh06+K/sItmkmgERW1ISFC2aeu739u1NW/HgwWZugogIM9lRz55m5IBleauNU3ZE\n3L/f9E0oWjR3fwfJGc89B7Vrm5UuU44+qVTJdBD86SdvELDnB1CTgOQj+rSK2NIbFhYRAZMnm7b/\nsWPNqofz5qWe7CjtRT8x0cxad+KEdyii5G+33GLmpAgKgl694PvvzfakJLMKIXibntxu1QRJvqMw\nIJKVli1h3TpYtQo+/th0ELOlt/BMTAz8+9+m42FW6yZI/mBZpsPo/Pmm/8hrr5man5QBUpMEST6m\nT69IVpKSzNN/mTIZH2NPQuPxmNnozp2Dl1/OvTKKzyQnJxOQtrbHDn2hoWZa6pUrvQtdiRQAqhkQ\nyUpgYNbVvvb+9983NQhdupgmBclXNm/ezN13382mTZtISm/BKrv2p3lz1fpIgaIwIOILlmVmHHz1\nVTOu/Nln/V0iuQKnTp2ie/fu1K9fn9jYWIoWLUqgphYWB1EYEPGFL74ws8yNGmWCQMoRCZJnJSUl\nER0dTUhICPPmzWPixIls2bKFsLAwfxdNJFepz4CIL1SrBhMnmtkMQSsX5gPr1q2jV69ebNmyhWef\nfZYxY8ZQqVIlfxdLxC9UMyDiC7Vre4MApAoCSUlJ/PTTTxw8eNAPBZO0jh8/TufOnYmIiCAgIID1\n69czY8YMBQFxNIUBkRwWEBDApEmTCA8PZ8SIEfzxxx/+LpIjJSYmMn78eEJCQli0aBFTp05lw4YN\nNGzY0N9FE/E7hQGRHOZyuRg5ciQDBw7krbfeIjQ0lAULFmClWK9g/fr1JGtFuxyzcuVKateuzaBB\ng+jUqRP79u2jS5cu6XcSFHEghQGRXFC8eHFGjx7Nrl27qFWrFu3bt6dVq1bs3r2bzZs3ExERQURE\nBJs2bfJ3UQuUo0eP8thjj9GiRQvKlSvHpk2biIqKoly5cv4umkieojAgkouCg4NZuHAhCxcu5PDh\nw9SsWZO2bdtiWRbfffcdDRo0oFu3bvz222/+Lmq+Fh8fT2RkJDVq1GDt2rX84x//YM2aNdSpU8ff\nRRPJkxQGRPygbdu27Ny5k0ceeYRffvnl8nbLspg6dSohISG899576U98I5n66quvCA8PZ+TIkfTs\n2ZO9e/fy97//HZdGd4hkSGFAxE8SEhJYs2ZNuvt+//13evbsSf369fn2229zuWT504EDB2jbti0P\nPPAA1apVY/v27YwdO5ZSpUr5u2gieZ7CgIifHDlyhKJZLHG8detW7r77bjp16pSqBkG8zp8/zyuv\nvEJ4eDg7duxgwYIFLFu2jNDQUH8XTSTfUBgQ8ZNatWoRExPDa6+9RlBQUKbH/uMf/6B69eqMGzeO\nRC2QA5gmlU8//ZQaNWowbtw4hgwZwu7du3n00UfVJCByhRQGRPyoaNGijBgxgt27d/PII49kemxs\nbCwDBw6kdu3arFixIpdKmDft2rWL5s2b8/jjj1O3bt3LoaqYpoEWuSoKAyJ5wC233MLnn3/O0qVL\nqZ7Faoe7d++mZcuWtG/fniNHjuRSCfOGs2fP0r9/f2rXrs1PP/3E4sWL+fLLL6lWrZq/iyaSrykM\niOQhrVq1Yvv27bz99tuUKFEi02MXLFhAaGgoo0ePJj4+PpdK6B/JycnMmjWL6tWr88EHHzB69Gh2\n7NhB69at/V00kQJBYUAkjylcuDCDBg1i7969dOzYMdNjL1y4wPDhwwkPD2fhwoWpZjUsKDZv3szd\nd9/NM888Q7Nmzdi7dy9DhgyhSJEi/i6aSIGhMCCSR914443Mnj2b1atXU6tWrUyPPXToEA8++CBt\n27Zl//79uVTCnHXq1Cm6d+9O/fr1iY2N5ZtvvmHevHlUrlzZ30UTKXAUBkTyuMaNG1+eRrdMmTKZ\nHrt48WJuv/12hg4dyvnz53OphL6VlJREdHQ0ISEhzJs3j4kTJ7JlyxaaNm3q76KJFFgKAyL5gNvt\npmfPnpcX2Mls6NzFixcZM2YMNWrUYP78+fmq6WDdunU0aNCAHj168NBDD7Fv3z769OmD2+32d9FE\nCjSFAZF8pEKFCpeX3v3rX/+a6bE//fQTHTp04N5772Xnzp25VMKrc/z4cTp37kxERAQBAQGsX7+e\nGTNmUKlSJX8XTcQRFAZE8qEGDRpcvmFWqFAh02NXrVpFnTp16NevH2fPns2lEmZPYmIi48ePJyQk\nhEWLFl0OOg0bNvR30UQcRWFAJJ8KCAjg2WefvVyVHhgYmOGxSUlJTJw4kZCQED766COSk5Ov+OfF\nxcWxd+9eAPbu3UtcXNxVlx1g5cqV1K5dm0GDBtGpU6fLTSCZ/R4ikjNcVn5qUBSRDO3YsYPevXvz\n31S9GFEAAAb6SURBVP/+N8tjGzZsSFRUFPXq1cv0uJiYGKKjo1m+eDF7Dx1K1f/A5XJRvVo1WrZp\nQ/fu3QkLC8tWOY8ePcqAAQP47LPPiIiIICoqSksLi/iZwoBIAWJZFvPnz2fAgAEcO3Ys02NdLhdd\nunQhMjKS8uXLp9p3+PBhXuzWja+XL6ei2007j4cGQBhQDPgDiAE2Agvcbn71eLi/ZUve++ADqlat\nmu7Pi4+PZ9y4cURGRlK6dGnGjh1Lx44dtY6ASF5giUiBExsbaw0ZMsQqVKiQBWT6VbZsWevdd9+1\nPB6PZVmWNW3aNKt4UJB1s9ttzQErASwrk68EsOaAVcXttooHBVnTpk37U3kWLlxoVatWzXK73dbA\ngQOts2fP5vZ/EhHJhGoGRAqwffv28dJLL/H1119neWydOnVo0KAB06ZN4wVgPFDyCn5WLNAfmA6M\nHj2aV155hQMHDtC3b18WLVpEixYtmDx5spYWFsmDFAZECjjLsli4cCF9+/bl8OHDWR7/OjDsGn7e\n68AIoE2bNqxYsYLrr7+eCRMm8Mgjj6hJQCSPUhgQcYgLFy4wduxYxowZk+7CRgHAs5gn+2thAV2A\nj4AXe/fmzTff1NLCInmchhaKOETRokUZMWIEu3fv5tFHH021LwC4AZjgg5/jwjQx/CUwkP179igI\niOQDCgMiDnPLLbewYMECli5dSvXq1QFIBt7G20dgB+bi8FWK922+tK1+mvO1Bhql2VYKGJOUxNfL\nl7N7924f/wYi4msKAyIO1apVK7Zv305ERATlgPYp9t0OlAFWp9i2BnPB2AbY0w1ZwHrgnnTO3w6o\n6Hbz/vvv+7zsIuJbCgMiDla4cGFOHT/OE0DhFNtdQAQmANjWAI9c2rfu0ratwDng7nTOXQRo5/Gw\nYskSn5dbRHxLYUDEwWJjY9l76BAN0tnXGNM0cOHS67VAG6A23pBg1xakFwbANCnsOXjwmqcuFpGc\npTAg4mAHDx7EsizSm0i4MZCIaQbYB5y8tK0J3jCwFjMrYZkMzh+OGdp44MABn5ZbRHxLYUDEwRIS\nEgAzxXBa9YEgTL+BNUBFIBgTCL4HLl7a3jiT8xdN83NEJG9y+7sAIuI/RYoUAcxaA2kVAv6KCQNV\n8N70GwMJwBzgBKamICN2E4P9c0Qkb1LNgIiDBQcH43K5iMlgf2NgA7AKbxi4DqgBvIXpTJhZzcAu\nzIJIwcHBvimwiOQIhQERBytRogTVq1VjYwb7G2Oe7n8k9U2/CaYfwS3AjZmc/39AjVtvpUSJEj4o\nrYjkFIUBEYdr2aYNC9xuLqaz7y4gEDOJUO0U2xtjagUyayJIwCxv3KJ1a5+VVURyhtYmEHG4mJgY\nwsPDmQM85cPzzgU6Xjq/VioUydsUBkSE1q1asfubb9jh8VzRssUZOQfUdLsJa9aMJcuW+eCMIpKT\nFAZEhMOHD1MzLIwn4+OZdo3nsoCuwLygIHbExFC1alUflFBEcpL6DIgIVatWZeKUKUwHRl/DeaxL\n758OTIqKUhAQySc0z4CIAPDCCy9w4sQJhg0bxhHMMsRX0mRwDhiACQKRkZE8//zzOVFMEckBaiYQ\nkVSmT59O3969uc7jYYzHQ3tSL2KUVgKwAPg/t5tTbjeToqIUBETyGYUBEfmTw4cP82K3bny9fDkV\n3W7aeTzUx6w1UBQz98AuzDwCC9xufvV4uL9lS9774AM1DYjkQwoDIpKhmJgYoqOjWbFkCXsuLWpk\nc7lc1Lj1Vlq0bk2PHj00fFAkH1MYEJFsiYuL48CBAyQkJFCkSBGCg4M1s6BIAaEwICIi4nAaWigi\nIuJwCgMiIiIOpzAgIiLicAoDIiIiDqcwICIi4nAKAyIiIg6nMCAiIuJwCgMiIiIOpzAgIiLicAoD\nIiIiDqcwICIi4nAKAyIiIg6nMCAiIuJwCgMiIiIOpzAgIiLicAoDIiIiDqcwICIi4nAKAyIiIg6n\nMCAiIuJwCgMiIiIOpzAgIiLicAoDIiIiDqcwICIi4nAKAyIiIg6nMCAiIuJwCgMiIiIOpzAgIiLi\ncAoDIiIiDqcwICIi4nAKAyIiIg6nMCAiIuJwCgMiIiIOpzAgIiLicAoDIiIiDqcwICIi4nAKAyIi\nIg6nMCAiIuJwCgMiIiIOpzAgIiLicAoDIiIiDqcwICIi4nAKAyIiIg6nMCAiIuJwCgMiIiIOpzAg\nIiLicAoDIiIiDqcwICIi4nAKAyIiIg6nMCAiIuJwCgMiIiIOpzAgIiLicAoDIiIiDqcwICIi4nAK\nAyIiIg6nMCAiIuJwCgMiIiIOpzAgIiLicAoDIiIiDqcwICIi4nAKAyIiIg6nMCAiIuJwCgMiIiIO\npzAgIiLicAoDIiIiDqcwICIi4nAKAyIiIg73/zzgIsvlm8XHAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x10c30f2e8>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# 描画(edgeに付いている数字は(capacity, 'flow')の意味)\n",
    "\n",
    "pos={'s':(0,2),'v':(3,4),'w':(3,0),'t':(6,2)}\n",
    "edge_labels = {(i, j): (w['capacity'], str((w['flow'])) ) for i, j, w in T.edges(data=True)}\n",
    "nx.draw_networkx_edge_labels(T, pos, edge_labels=edge_labels, font_color='r')\n",
    "nx.draw_networkx_labels(T, pos)\n",
    "nx.draw(T, pos)\n",
    "plt.axis('off')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# The Edmonds-Karp Algorithm: Shortest Augmenting Paths"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ford-Fulkerson algorithmではpathの選び方を特に定めていなかった。（そのため、pseudopolynomial-time algorithmになっている。）*Edmonds-Karp algorithm*では、もう少し「賢く」　i.e. the shortest augmenting pathになるようにpathを選ぶ。こちらは、$O(m^2n)$ timeのalgorithmになっている。\n",
    "\n",
    "BFSを用いればpathは自然とshortestになるので、前回作った*fordFulkerson*は実は*Edmonds-Karp algorithm*にもなっている。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Dinic's Algorithm: Blocking Flows"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "BFSを用いてblocking flowsを求めると$O(m^2)$の時間がかかるが、Problem Sets #1 にあるDFSを持ちいた方法を用いれば$O(mn)$の時間で求められるらしい。Lemma 4.2と併せれば、Dinic's algorithmの所要時間は$O(mn^2)$となり、EK algorithmより効率的なalgorithmになる。\n",
    "\n",
    "実装は後日余裕があれば。"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [default]",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  },
  "toc": {
   "nav_menu": {
    "height": "66px",
    "width": "252px"
   },
   "navigate_menu": true,
   "number_sections": true,
   "sideBar": true,
   "threshold": 4,
   "toc_cell": true,
   "toc_number_sections": true,
   "toc_section_display": "block",
   "toc_threshold": 6,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}