|
# The following adjacency matrix includes a super source `i1` and a super sink `o1`. |
|
# This allows us to implement max-flow where there is one source and sink. |
|
# The edge weights used are the sums of all outgoing edge weights for the original sources |
|
# and the sums for all incoming edge weights for the original sinks. |
|
GRAPH = [ |
|
#i1 A B C D E F G H I J K L M N O P o1 |
|
[0, 40, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 105, 0, 0, 0, 0, 0], #i1 |
|
[0, 0, 0, 0, 0, 23, 17, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], #A |
|
[0, 23, 0, 20, 0, 0, 0, 30, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], #B |
|
[0, 0, 0, 0, 4, 0, 0, 18, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0], #C |