Проблема с проточной сетью
Вы взорвали устройство судного дня LAMBCHOP и вырвали кроликов из тюрьмы Лямбды — и теперь вам нужно сбежать с космической станции как можно быстрее и организованнее! Все кролики собрались в разных местах по всей станции, и им нужно пробиться к, казалось бы, бесконечному количеству спасательных капсул, расположенных в других частях станции. Вам нужно провести многочисленных кроликов через различные комнаты к спасательным капсулам. К сожалению, в коридорах между комнатами одновременно может поместиться только определенное количество кроликов. Более того, размер многих коридоров был изменен, чтобы вместить ЯГНЯКА, поэтому они различаются по количеству кроликов, которые могут перемещаться по ним одновременно.
Учитывая начальные номера комнат групп кроликов, номера комнат спасательных капсул и количество кроликов, которые могут пройти одновременно в каждом направлении каждого коридора между ними, выясните, сколько кроликов может безопасно добраться до побега. стручки за раз на пике.
Напишите функциональное решение (входы, выходы, путь), которое принимает массив целых чисел, обозначающих, где находятся группы собранных кроликов, массив целых чисел, обозначающих, где расположены спасательные капсулы, и массив массива целых чисел коридоров, возвращает общее количество кроликов, которые могут пройти на каждом временном шаге, как int. Входы и выходы не пересекаются и поэтому никогда не пересекаются. Путь элемента пути[A][B] = C описывает, что коридор, идущий от A до B, может вместить C кроликов на каждом временном шаге. Есть не более 50 комнат, соединенных коридорами, и не более 2000000 кроликов, которые могут поместиться одновременно.
Тестовые кейсы
Ввод: Solution.solution ({0, 1}, {4, 5}, {{0, 0, 4, 6, 0, 0}, {0, 0, 5, 2, 0, 0}, {0, 0 , 0, 0, 4, 4}, {0, 0, 0, 0, 6, 6}, {0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0 }})
Вывод: 16
Ввод: Solution.solution ({0}, {3}, {{0, 7, 0, 0}, {0, 0, 6, 0}, {0, 0, 0, 8}, {9, 0, 0 , 0}})
Вывод: 6
Решение алгоритма Динича
import java.util.List;
import java.util.ArrayList;
import java.util.Queue;
import java.util.ArrayDeque;
import java.util.Arrays;
public class Solution {
private static final int INF = 20000;
private static class Edge {
public int from, to;
public Edge residual;
public int flow;
public final int capacity;
public Edge(int from, int to, int capacity) {
this.from = from;
this.to = to;
this.capacity = capacity;
}
public boolean isResidual() {
return capacity == 0;
}
public int remainingCapacity() {
return capacity - flow;
}
public void augment(int bottleNeck) {
flow += bottleNeck;
residual.flow -= bottleNeck;
}
}
private abstract static class NetworkFlowSolverBase {
// Inputs: n = number of nodes, s = source, t = sink
final int n, s, t;
// Indicates whether the network flow algorithm has ran. The solver only
// needs to run once because it always yields the same result.
protected boolean solved;
// The maximum flow. Calculated by calling the {@link #solve} method.
protected int maxFlow;
// The adjacency list representing the flow graph.
protected List<Edge>[] graph;
/**
* Creates an instance of a flow network solver. Use the {@link #addEdge} method to add edges to
* the graph.
*
* @param n - The number of nodes in the graph including s and t.
* @param s - The index of the source node, 0 <= s < n
* @param t - The index of the sink node, 0 <= t < n and t != s
*/
public NetworkFlowSolverBase(int n, int s, int t) {
this.n = n;
this.s = s;
this.t = t;
initializeEmptyFlowGraph();
}
// Constructs an empty graph with n nodes including s and t.
@SuppressWarnings("unchecked")
private void initializeEmptyFlowGraph() {
graph = new List[n];
for (int i = 0; i < n; i++) {
graph[i] = new ArrayList<Edge>();
}
}
/**
* Adds a directed edge (and its residual edge) to the flow graph.
*
* @param from - The index of the node the directed edge starts at.
* @param to - The index of the node the directed edge ends at.
* @param capacity - The capacity of the edge
*/
public void addEdge(int from, int to, int capacity ) {
if ( capacity <= 0 ) {
throw new IllegalArgumentException("Forward edge capacity <= 0");
}
Edge e1 = new Edge(from, to, capacity);
Edge e2 = new Edge(to, from, 0);
e1.residual = e2;
e2.residual = e1;
graph[from].add(e1);
graph[to].add(e2);
}
/**
* Returns the residual graph after the solver has been executed. This allows you to inspect the
* {@link Edge#flow} and {@link Edge#capacity} values of each edge. This is useful if you are
* debugging or want to figure out which edges were used during the max flow.
*/
public List<Edge>[] getGraph() {
execute();
return graph;
}
// Returns the maximum flow from the source to the sink.
public int getMaxFlow() {
execute();
return maxFlow;
}
// Wrapper method that ensures we only call solve() once
private void execute() {
if (solved) return;
solved = true;
solve();
}
// Method to implement which solves the network flow problem.
public abstract void solve();
}
private static class DinicsSolver extends NetworkFlowSolverBase {
private int[] level;
/**
* Creates an instance of a flow network solver.
*
* Use the {@link #addEdge} method to add edges to
* the graph.
*
* @param n - The number of nodes in the graph including
* source and sink nodes.
* @param s - The index of the source node,
* 0 <= s < n
* @param t - The index of the sink node,
* 0 <= t < n, t != s
*/
public DinicsSolver(int n, int s, int t) {
super(n, s, t);
level = new int[n];
}
@Override
public void solve() {
// next[i] indicates the next edge index to take in the adjacency list for node i. This is
// part
// of the Shimon Even and Alon Itai optimization of pruning deads ends as part of the DFS
// phase.
int[] next = new int[n];
while ( bfs() ) {
Arrays.fill(next, 0);
// Find max flow by adding all augmenting path flows.
for ( int f = dfs(s, next, INF); f != 0; f = dfs(s, next, INF)) {
maxFlow += f;
}
}
}
// Do a BFS from source to sink and compute the depth/level of each node
// which is the minimum number of edges from that node to the source.
private boolean bfs() {
Arrays.fill(level, -1);
Queue<Integer> q = new ArrayDeque<>(n);
q.offer(s);
level[s] = 0;
while ( !q.isEmpty() ) {
int node = q.poll();
for (Edge edge : graph[node]) {
if ( edge.remainingCapacity() > 0
&& level[edge.to] == -1) {
level[edge.to] = level[node] + 1;
q.offer(edge.to);
}
}
}
// Return whether we were able to reach the sink node.
return level[t] != -1;
}
private int dfs(int at, int[] next, int flow) {
if ( at == t ) {
return flow;
}
final int numEdges = graph[at].size();
while ( next[at] < numEdges ) {
Edge edge = graph[at].get(next[at]);
int cap = edge.remainingCapacity();
if ( cap > 0 && level[edge.to] == level[at] + 1) {
int bottleNeck = dfs(edge.to, next, flow > cap ? cap : flow);
if ( bottleNeck > 0 ) {
edge.augment(bottleNeck);
return bottleNeck;
}
}
next[at]++;
}
return 0;
}
}
public static int solution(int[] entrances, int[] exits, int[][] path) {
// Setup all nodes with an extra source and sink
int pathLen = path.length;
int totalNodes = pathLen + 2;
int source = totalNodes - 1;
int exit = totalNodes - 2;
NetworkFlowSolverBase solver;
solver = new DinicsSolver(totalNodes, source, exit);
// Add edges from source to entrances
for (int i : entrances) {
solver.addEdge(source, i, INF);
}
// Add edges from exists to sink
for (int j : exits) {
solver.addEdge(j, exit, INF);
}
int noExitNodes = pathLen-exits.length;
// Add edges with values > 0
for ( int i = 0; i <= noExitNodes; i++ ) {
for ( int j = 0; j < pathLen; j++ ) {
// Remove all exit rows as all exit rows
// contains 0 values
if ( path[i][j] > 0 ) {
solver.addEdge(i, j, path[i][j]);
}
}
}
return solver.getMaxFlow();
}
}
Можно ли еще провести оптимизацию?