UVA820

Internet Bandwidth

On the Internet, machines (nodes) are richly interconnected, and many paths may exist between a given pair of nodes. The total message-carrying capacity (bandwidth) between two given nodes is the maximal amount of data per unit time that can be transmitted from one node to the other. Using a technique called packet switching, this data can be transmitted along several paths at the same time.
For example, the following figure shows a network with four nodes (shown as circles), with a total of five connections among them. Every connection is labeled with a bandwidth that represents its data-carrying capacity per unit time.

In our example, the bandwidth between node 1 and node 4 is 25, which might be thought of as the sum of the bandwidths 10 along the path 1-2-4, 10 along the path 1-3-4, and 5 along the path 1-2-3-4. No other combination of paths between nodes 1 and 4 provides a larger bandwidth.
You must write a program that computes the bandwidth between two given nodes in a network, given the individual bandwidths of all the connections in the network. In this problem, assume that the bandwidth of a connection is always the same in both directions (which is not necessarily true in the real world).

Input 

The input file contains descriptions of several networks. Every description starts with a line containing a single integer n (2 ≤n ≤100), which is the number of nodes in the network. The nodes are numbered from 1 to n. The next line contains three numbers s, t, and c. The numbers s and t are the source and destination nodes, and the number c is the total number of connections in the network. Following this are c lines describing the connections. Each of these lines contains three integers: the first two are the numbers of the connected nodes, and the third number is the bandwidth of the connection. The bandwidth is a non-negative number not greater than 1000.
There might be more than one connection between a pair of nodes, but a node cannot be connected to itself. All connections are bi-directional, i.e. data can be transmitted in both directions along a connection, but the sum of the amount of data transmitted in both directions must be less than the bandwidth.
A line containing the number 0 follows the last network description, and terminates the input.

Output 

For each network description, first print the number of the network. Then print the total bandwidth between the source node s and the destination node t, following the format of the sample output. Print a blank line after each test case.

Sample Input	Output for the Sample Input
4 1 4 5 1 2 20 1 3 10 2 3 5 2 4 10 3 4 20 0	Network 1 The bandwidth is 25.

大意: 網路流問題 給一平面無向圖(無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