M.rar_The First_maxflow_weight

package moduloVII; import java.io.*; import java.util.StringTokenizer; public class M { static final int WHITE = 0, GRAY = 1; static double[][] flow; static int[][] capacity; static double[][] res_capacity; static int[] parent, color, queue; static double[] min_capacity; static int first, last; public static void main(String args[]) { String frase; while ( ((frase=readLn(20))!=null) ) { StringTokenizer linha= new StringTokenizer(frase.trim()); int n=Integer.parseInt(linha.nextToken()); //Num de vertices int m=Integer.parseInt(linha.nextToken()); //Num de liga僖es capacity=new int[n+1][n+1]; //Vertice de Origem | Vertice de Destino | Peso da liga頒o for(int i=0; i<m; i++){ StringTokenizer le= new StringTokenizer(readLn(50).trim()); int origem= Integer.parseInt(le.nextToken()); int destino= Integer.parseInt(le.nextToken()); int pesoLigacao=Integer.parseInt(le.nextToken()); capacity[origem][destino] = pesoLigacao; } //Argumentos: origem, destino, tamanho int maxFlow=EdmondsKarp(1, n, n+1); System.out.println(maxFlow); } } public static int EdmondsKarp(int origem, int destino, int tam){ int max_flow=0; flow = new double[tam][tam]; res_capacity = new double[tam][tam]; parent = new int[tam]; min_capacity = new double[tam]; color = new int[tam]; queue = new int[tam]; for (int i = 0; i < tam; i++) for (int j = 0; j < tam; j++) res_capacity[i][j] = capacity[i][j]; while (BFS(origem, destino, tam)){ max_flow += min_capacity[destino]; int v = destino, u; while (v != origem){ u = parent[v]; flow[u][v] += min_capacity[destino]; flow[v][u] -= min_capacity[destino]; res_capacity[u][v] -= min_capacity[destino]; res_capacity[v][u] += min_capacity[destino]; v = u; } } return max_flow; } // Breadth First Search public static boolean BFS(int origem, int destino, int tam){ for (int i = 0; i < tam; i++){ color[i] = WHITE; min_capacity[i] = Double.MAX_VALUE; } first = last = 0; queue[last++] = origem; color[origem] = GRAY; while (first != last){ // While "queue" not empty.. int v = queue[first++]; for (int u = 0; u < tam; u++) if (color[u] == WHITE && res_capacity[v][u] > 0){ min_capacity[u] = Math.min(min_capacity[v], res_capacity[v][u]); parent[u] = v; color[u] = GRAY; if (u == destino) return true; queue[last++] = u; } } return false; } static String readLn (int maxLg){ byte lin[] = new byte [maxLg]; int lg = 0, car = -1; String line = ""; try { while (lg < maxLg){ car = System.in.read(); if ((car < 0) || (car == '\n')) break; lin [lg++] += car; } } catch (IOException e){ return (null); } if ((car < 0) && (lg == 0)) return (null); // eof return (new String (lin, 0, lg)); } }