Route Redundancy 这是怎么实现的呢

Question

Problem Description
A city is made up exclusively of one-way steets.each street in the city has a capacity,which is the minimum of the capcities of the streets along that route.

The redundancy ratio from point A to point B is the ratio of the maximum number of cars that can get from point A to point B in an hour using all routes simultaneously,to the maximum number of cars thar can get from point A to point B in an hour using one route.The minimum redundancy ratio is the number of capacity of the single route with the laegest capacity.

Input
The first line of input contains asingle integer P,(1<=P<=1000),which is the number of data sets that follow.Each data set consists of several lines and represents a directed graph with positive integer weights.

The first line of each data set contains five apace separatde integers.The first integer,D is the data set number. The second integer,N(2<=N<=1000),is the number of nodes inthe graph. The thied integer,E,(E>=1),is the number of edges in the graph. The fourth integer,A,(0<=A<N),is the index of point A.The fifth integer,B,(o<=B<N,A!=B),is the index of point B.

The remaining E lines desceibe each edge. Each line contains three space separated in tegers.The First integer,U(0<=U<N),is the index of node U. The second integer,V(0<=v<N,V!=U),is the node V.The third integer,W (1<=W<=1000),is th capacity (weight) of path from U to V.

Output
For each data set there is one line of output.It contains the date set number(N) follow by a single space, followed by a floating-point value which is the minimum redundancy ratio to 3 digits after the decimal point.

Sample Input
1
1 7 11 0 6
0 1 3
0 3 3
1 2 4
2 0 3
2 3 1
2 4 2
3 4 2
3 5 6
4 1 1
4 6 1
5 6 9

Sample Output
1 1.667

Answer 1

以下回答参考 皆我百晓生、券券喵儿 等免费微信小程序相关内容作答，并由本人整理回复。

# read the input file
input <- readLines("input.txt")

# split the input into individual data sets
data_sets <- unlist(lapply(split(input, "\n\n"), function(x) strsplit(x, " ")[[1]]))

# initialize variables
output <- numeric(length(data_sets))
redundancy_ratio <- numeric(length(data_sets))

# loop through each data set
for(i in 1:length(data_sets)) {
  # read the data for this data set
  data <- data_sets[[i]]
  
  # initialize variables for this data set
  N <- as.integer(strsplit(data, " ")[[1]][[1]])
  E <- as.integer(strsplit(data, " ")[[1]][[2]])
  A <- as.integer(strsplit(data, " ")[[1]][[3]])
  B <- as.integer(strsplit(data, " ")[[1]][[4]])
  
  # create a list of all possible routes between points A and B
  routes <- list()
  for(u in 1:N){
    for(v in u+1:N){
      if(u != v){
        routes[[u, v]] <- list(route = c(u, v), capacity = 1)
      }
    }
  }
  
  # calculate the redundancy ratio for this data set
  redundancy_ratio[i] <- min(max(routes[A, B], key=lambda(x: x$capacity))$capacity / max(routes[A, B], key=lambda(x: x$capacity))$capacity)
  
  # add the output for this data set
  output[i] <- sprintf("%d %.2f", i + 1, redundancy_ratio[i])
}

# print the output
print(output)