CH16 Bus

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.StringTokenizer;

/*
 * Tuenti Contest
 * Challenge 16 - Bus Stations
 * Author: Pedro Antonio Pardal Jimena
 * Email: pardal@alu.uma.es
 */

public class BusStations
{
    private static int bfs( int[][] capacidades, int[] camino, int[] padres, int inicio, int fin )
    {
        camino[inicio] = Integer.MAX_VALUE;

        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add( inicio );

        while ( !queue.isEmpty() )
        {
            int u = queue.poll();

            for ( int v = 0; v < capacidades.length; v++ )
            {
                if ( capacidades[u][v] != Integer.MAX_VALUE ) /* Hay arco */
                {
                    /* Hay capacidad suficiente, y v no fue visitado antes */
                    if ( capacidades[u][v] > 0 && padres[v] == -1 )
                    {
                        padres[v] = u;
                        camino[v] = Math.min( camino[u], capacidades[u][v] );

                        if ( v != fin )
                            queue.add( v );
                        else
                            return camino[fin];
                    }
                }
            }
        }

        return 0;
    }

    private static int edmondsKarp( int[][] capacidades, int tam, int inicio, int fin )
    {
        int maxFlujo = 0;
        int[][] flujos = new int[tam][tam];
        for ( int i = 0; i < tam; i++ )
            for ( int j = 0; j < tam; j++ )
                flujos[i][j] = 0;

        while ( true )
        {
            int[] camino = new int[tam];
            int[] padres = new int[tam];
            /* Inicializar tabla de padres */
            for ( int i = 0; i < padres.length; i++ )
            {
                padres[i] = -1;
            }
            padres[inicio] = -2; /* Para que el nodo inicial no sea redescubierto */

            /* Calcular un camino del nodo inicial al final en el grafo residual */
            int m = bfs( capacidades, camino, padres, inicio, fin );

            if ( m == 0 ) /* Si no hay camino, hemos terminado */
                break;

            maxFlujo += m;

            /* Actualizar el grafo residual con el menor arco del camino */
            int v = fin;

            while ( v != inicio )
            {
                int u = padres[v];
                capacidades[u][v] -= m;
                capacidades[v][u] += m;
                v = u;
            }
        }

        return maxFlujo;
    }

    public static void main( String[] args )
    {
        try
        {
            BufferedReader reader = new BufferedReader( new InputStreamReader( System.in ) );

            while ( reader.ready() )
            {
                String linea = reader.readLine();

                StringTokenizer st = new StringTokenizer( linea, " " );

                int tam = Integer.parseInt( st.nextToken() );
                String inicio = st.nextToken();
                String fin = st.nextToken();

                int[][] capacidades = new int[tam][tam];
                for ( int i = 0; i < tam; i++ )
                    for ( int j = 0; j < tam; j++ )
                        capacidades[i][j] = Integer.MAX_VALUE;

                Map<String, Integer> nodos = new HashMap<String, Integer>();
                nodos.put( inicio, 0 );
                nodos.put( fin, 1 );

                while ( st.hasMoreTokens() )
                {
                    String arco = st.nextToken();

                    StringTokenizer st2 = new StringTokenizer( arco, "," );

                    String desde = st2.nextToken();
                    String hasta = st2.nextToken();
                    int capacidad = Integer.parseInt( st2.nextToken() );

                    if ( !nodos.containsKey( desde ) )
                        nodos.put( desde, nodos.size() );

                    if ( !nodos.containsKey( hasta ) )
                        nodos.put( hasta, nodos.size() );

                    int desdeIdx = nodos.get( desde );
                    int hastaIdx = nodos.get( hasta );

                    capacidades[desdeIdx][hastaIdx] = capacidad;
                }

                int result = edmondsKarp( capacidades, tam, 0, 1 );

                System.out.println( result );
            }
        }
        catch ( Exception e )
        {
            System.err.println( "Error en el formato de entrada." );
            e.printStackTrace( System.err );
        }
    }
}