m.java

Implementation of Edmonds Karp algorithm that calculates maxFlow of graph. Input: For each test c

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));
	}
}