#!/usr/bin/python
import sys
import collections
INF = 10000000
def read_testcase(fin):
N, source, sink, L = [int(x) for x in fin.readline().strip().split(" ")]
capacity = []
for _ in range(N):
line = fin.readline().strip().split(" ")
capacity.append([int(x) for x in line])
return N, source, sink, L, capacity
def list_testcases(fin):
cases = int(fin.readline().strip())
for _ in range(cases):
fin.readline()
yield read_testcase(fin)
def solve_testcase(N, source, sink, L, capacity):
if L == 1:
return capacity[source][sink]
if L == 2:
return capacity[source][sink] + sum(min(capacity[source][i], capacity[i][sink]) for i in range(N))
assert L == 3
# Use maxflow to solve the problem
source_neighb = [i for i in range(N) if capacity[source][i] and i != sink]
sink_neighb = [i for i in range(N) if capacity[i][sink] and i != source]
# We will number nodes in new graph as following
# s -> s
# x = neighb s -> x
# y = neight t -> y + N
# t -> t + N
# Build initial residual graph
residual = collections.defaultdict(dict)
residual[source][sink + N] = capacity[source][sink]
residual[sink + N][source] = 0
for i in range(N):
# s -> neighbour s
if i in source_neighb:
residual[source][i] = capacity[source][i]
residual[i][source] = 0
# self-loop
if i in source_neighb and i in sink_neighb:
residual[i][N+i] = INF
residual[N+i][i] = 0
# neighbour t -> t
if i in sink_neighb:
residual[N+i][N+sink] = capacity[i][sink]
residual[N+sink][N+i] = 0
for i in source_neighb:
for j in sink_neighb:
if i == j or not capacity[j][sink]:
continue
residual[i][N+j] = capacity[i][j]
residual[N+j][i] = 0
def find_path(residual):
"""Find path in residual graph
"""
reachable = {} # reachable vertices, along with their associated paths
pending = []
def search_from(u):
for v in residual[u].keys():
if v in reachable or not residual[u][v]]:
# if already visited or not capacity, do nothing
continue
reachable[v] = reachable[u] + [v] # store path
pending.append(i)
reachable[source] = [source]
pending.append(source)
while pending:
u = pending.pop()
search_from(u)
if N + sink in reachable:
return reachable[N + sink]
return None
total_flow = 0
while True:
path = find_path(residual)
if not path:
break
edge_list = list(zip(path[:-1], path[1:]))
# find maximum we can push
flow = min(residual[u][v] for u,v in edge_list)
# push it along the path
for u,v in edge_list:
residual[u][v] -= flow
residual[v][u] += flow
total_flow += flow
return total_flow
if __name__ == "__main__":
for params in list_testcases(sys.stdin):
print 1.0 / 8 * solve_testcase(*params)