大意: 網路流問題 給一平面無向圖(無cycle) 問你從起點到終點的最大總流量為多少
※There might be more than one connection between a pair of nodes, 
but a node cannot be connected to itself.

解法: Edmonds-Karp Algorithm




import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class UVA820 {

 public static void main(String[] args) {

  Scanner sc = new Scanner(System.in);

  int count = 1;
  int size = 0;

  while (sc.hasNext()) {

   size = sc.nextInt();

   if (size == 0)
    break;

   System.out.println("Network " + count);
   count++;

   int map[][] = new int[size+1][size+1];
   int record_map[][] = new int[size+1][size+1];
   int parent[] = new int[size+1];
   Queue<Integer> qi = new LinkedList<Integer>();

   int source = sc.nextInt();

   int sink = sc.nextInt();

   int line = sc.nextInt();

   for (int l = 0; l < line; l++) {

    int line_s = sc.nextInt();

    int line_d = sc.nextInt();

    int line_f = sc.nextInt();

    // There might be more than one connection between a pair of nodes, but a node cannot be connected to itself.
    map[line_s][line_d] += line_f;

    map[line_d][line_s] = map[line_s][line_d];

   }

   int flow = 0;

   while (true) {

    int source_w[] = new int[size+1];

    source_w[source] = Integer.MAX_VALUE;

    qi.offer(source);

    while (!qi.isEmpty()){

     int start;

     start = qi.poll();

     for (int next = 1; next <= size && start!=sink; next++){

      if (map[start][next] > record_map[start][next]
        && source_w[next] == 0) {
       parent[next] = start;
       qi.offer(next);

       source_w[next] = source_w[start] < map[start][next]
         - record_map[start][next] ? source_w[start]
         : map[start][next]
           - record_map[start][next];
      }
     }
    }

    if (source_w[sink] == 0)
     break;

    for (int back = sink; back != source; back = parent[back]) {
     record_map[parent[back]][back] += source_w[sink];
     record_map[back][parent[back]] -= source_w[sink];
    }

    flow += source_w[sink];
   }

   System.out.println("The bandwidth is " + flow + ".");
   System.out.println();

  }

  sc.close();
 }
}

// s:start
// d:destination
// f:flow