import java.util.*;

public class Virtaustutkimus {
    public static final int HAKU = 2; // 1 = leveyshaku, 2 = syvyyshaku
    public static final int KOKO = 500;
    public static int[][] verkko = new int[KOKO+1][KOKO+1];
    public static int alku = 1;
    public static int loppu = 100;
    public static int virtaus = 0;

    public static class JononSolmu {
        public int tunnus;
        public JononSolmu vanha;

        public JononSolmu(int tunnus, JononSolmu vanha) {
            this.tunnus = tunnus;
            this.vanha = vanha;
        }
    }

    public static LinkedList<Integer> reitti;
    public static TreeSet<Integer> mukana;
    public static LinkedList<JononSolmu> jono;
    public static int lisays;

    public static void etsiReitti() {
        jono.addLast(new JononSolmu(alku, null));
        while (jono.size() > 0) {
            JononSolmu solmu = jono.removeFirst();
            if (solmu.tunnus == loppu) {
                lisays = verkko[solmu.vanha.tunnus][solmu.tunnus];
                while (true) {
                    reitti.addFirst(solmu.tunnus);
                    if (solmu.vanha == null) break;
                    lisays = Math.min(lisays, verkko[solmu.vanha.tunnus][solmu.tunnus]);
                    solmu = solmu.vanha;
                }
                return;
            }
            for (int uusi = 1; uusi <= KOKO; uusi++) {
                if (verkko[solmu.tunnus][uusi] > 0 && !mukana.contains(uusi)) {
                    mukana.add(uusi);
                    jono.addLast(new JononSolmu(uusi, solmu));
                }
            }
        }
    }

    public static void etsiReitti(int solmu, int pienin) {
        if (lisays > 0) return;
        if (mukana.contains(solmu)) return;
        reitti.addLast(solmu);
        mukana.add(solmu);
        if (solmu == loppu) {
            lisays = pienin;
        }
        for (int uusi = 1; uusi <= KOKO; uusi++) {
            if (verkko[solmu][uusi] > 0) {
                int uusiPienin = pienin;
                if (pienin == 0 || verkko[solmu][uusi] < pienin) {
                    uusiPienin = verkko[solmu][uusi];
                }
                etsiReitti(uusi, uusiPienin);
            }
        }
        if (lisays == 0) reitti.removeLast();
    }

    public static void main(String[] args) {
        Random arpoja = new Random(123);
        for (int i = 1; i <= KOKO; i++) {
            for (int j = 1; j <= KOKO; j++) {
                if (i == j) continue;
                verkko[i][j] = arpoja.nextInt(100);
            }
        }
        while (true) {
            reitti = new LinkedList<Integer>();
            mukana = new TreeSet<Integer>();
            jono = new LinkedList<JononSolmu>();
            lisays = 0;
            if (HAKU == 1) etsiReitti();
            if (HAKU == 2) etsiReitti(alku, 0);
            if (lisays == 0) break;
            //System.out.println("Reitti: " + reitti);
            //System.out.println("Lisäys: " + lisays);
            virtaus += lisays;
            for (int i = 0; i < reitti.size()-1; i++) {
                verkko[reitti.get(i)][reitti.get(i+1)] -= lisays;
                verkko[reitti.get(i+1)][reitti.get(i)] += lisays;
            }
        }
        System.out.println("Maksimivirtaus: " + virtaus);
    }
}