跳到主要內容

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 InputOutput 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










標籤：

留言

張貼留言

這個網誌中的熱門文章

UVA11349

J - Symmetric Matrix Time Limit: 1 sec Memory Limit: 16MB You`re given a square matrix M. Elements of this matrix are M ij : {0 < i < n, 0 < j < n}. In this problem you'll have to find out whether the given matrix is symmetric or not. Definition: Symmetric matrix is such a matrix that all elements of it are non-negative and symmetric with relation to the center of this matrix. Any other matrix is considered to be non-symmetric. For example: All you have to do is to find whether the matrix is symmetric or not. Elements of a matrix given in the input are -2 32  <= M ij  <= 2 32  and 0 < n <= 100. INPUT: First line of input contains number of test cases T <= 300. Then T test cases follow each described in the following way. The first line of each test case contains n - the dimension of square matrix. Then n lines follow each of then containing row i. Row contains exactly n elements separated by a space character. j-th number in row i i...
張貼留言
閱讀完整內容

UVA11461

A square number is an integer number whose square root is also an integer. For example 1, 4, 81 are some square numbers. Given two numbers a and b you will have to find out how many square numbers are there between a and b (inclusive). Input The input file contains at most 201 lines of inputs. Each line contains two integers a and b (0 < a ≤ b ≤ 100000). Input is terminated by a line containing two zeroes. This line should not be processed. Output For each line of input produce one line of output. This line contains an integer which denotes how many square numbers are there between a and b (inclusive). Sample Input 1 4 1 10 0 0 Sample Output 2 3 大意:給兩個數字 求範圍內平方不大於第二個數字的數量 解法: 以最大數取根號後往回看 import java.util.Scanner; public class UVA11461 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { int start = sc.nextInt(); int last = sc.nextInt(); if (last == 0) break; System.o...
張貼留言
閱讀完整內容

UVA11005

Problem B Cheapest Base Input:  Standard Input Output:  Standard Output When printing text on paper we need ink. But not every character needs the same amount of ink to print: letters such as 'W', 'M' and '8' are more expensive than thinner letters as ' i ', 'c' and '1'. In this problem we will evaluate the cost of printing numbers in several bases. As you know, numbers can be expressed in several different bases. Well known bases are binary (base 2; digits 0 and 1), decimal (base 10; digits 0 to 9) and hexadecimal (base 16; digits 0 to 9 and letters A to F). For the general base  n  we will use the first  n  characters of the string "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ", which means the highest base in this problem is 36. The lowest base is of course 2. Every character from this string has an associated cost, represented by an integer value between 1 and 128. The cost to print a number in a certain base is the s...
張貼留言
閱讀完整內容