1. 

/**
* FWP: Ausgewaehlte Probleme aus dem ACM (SS10)
*
* Method: Networks: Max flow - Edmond Karp
* Problem: 820 - InternetBandwith
* Accepted: 0.670
* @author Evgeni Pavlidis

*/
import java.io.*;
import java.util.*;

class Main {

private static int vertices, edges, networkNumber = 1;

// saves the max capacity between [v1,v2]
private static int[][] m;
// saves a set of neighbours of v
private static List<Set<Integer>> neighbors;
// saves the parents of v
private static int[] parent;
// saves the flow for (source, sink)
private static int[][] F;

private static int edmondsKarp(int source, int sink)
{
int f = 0, flow, v, u;
F = new int[vertices][vertices];
neighbors = new ArrayList<Set<Integer>>();
parent = new int[vertices];

// init neighbours sets
for(v = 0; v < vertices; v++)
{
neighbors.add(new HashSet<Integer>());
for(int v2 = 0; v2 < vertices; v2++)
if(v != v2 && m[v][v2] > 0)
neighbors.get(v).add(v2);
}

while(true)
{
// get updated max flow
flow = bfs(source, sink);
if(flow == 0)
break;

// accumulate flow
f += flow;

v = sink;
while(v != source)
{
u = parent[v];
F[u][v] += flow;
F[v][u] -= flow;
v = u;
}
}
return f;
}

private static int bfs(int source, int sink)
{
int v;
int[] capacity = new int[vertices];

Queue<Integer> queue = new LinkedList<Integer>();

for(v = 0; v < vertices; v++)
parent[v] = -1;

parent[source] = -2;
capacity[source] = Integer.MAX_VALUE;
queue.add(source);

while(queue.size() > 0)
{
v = queue.remove();
for(int n: neighbors.get(v))
if((m[v][n] - F[v][n] > 0) && parent[n] == -1)
{
parent[n] = v;
capacity[n] = Math.min(capacity[v], m[v][n] - F[v][n]);
if(n == sink) // max flow to sink found
return capacity[sink];

queue.add(n);
}
}

return 0;
}


public static void main(String...args)
{
Scanner scanner = new Scanner(System.in);

int start, end;
int v1, v2, dist;

while(true)
{
vertices = scanner.nextInt();
if(vertices == 0)
break;

start = scanner.nextInt()-1;
end = scanner.nextInt()-1;
edges = scanner.nextInt();

m = new int[edges][edges];

for(int e=0; e < edges; e++)
{
v1 = scanner.nextInt()-1;
v2 = scanner.nextInt()-1;
dist = scanner.nextInt();
m[v1][v2] += dist;
m[v2][v1] += dist;
}

System.out.println("Network " + networkNumber++);
System.out.printf("The bandwidth is %d.\n\n", edmondsKarp(start, end));

}
}
}