Panic Room

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
 This problem has been solved by hjfreyer.

 Sorter: hjfreyer Unknown http://acm.pku.edu.cn/JudgeOnline/problem?id=3084

Panic Room is problem number 3084 on the Peking University ACM site. This is a Max Flow/Min Cut problem solved with the Ford-Fulkerson algorithm.

Solution

```import java.util.*;

public class Main{
public static Scanner in;

public static void main(String[] args){
in =new Scanner(System.in);

doStuff();
}

public static void doStuff(){
int N=in.nextInt();

for(int i=0; i<N; i++){
new Instance();
}
}

static class Instance {
int rooms;
int panic;

Set<Integer> intruded = new HashSet<Integer>();

double[][] graph;
int nodeCount;

public Instance() {
rooms = in.nextInt();
panic = in.nextInt();

List<Map<Integer, Integer>> roomsWithPanelsTo =
new ArrayList<Map<Integer, Integer>>();

int edges = 0;

for (int i = 0; i < rooms; i++) {
if (in.next().equals("I"))

Map<Integer, Integer> doorCounts =
new HashMap<Integer, Integer>();

int c = in.nextInt();
for(int j = 0; j < c; j++) {
int other = in.nextInt();

if (doorCounts.containsKey(other))
doorCounts.put(other, doorCounts.get(other) + 1);
else {
edges++;
doorCounts.put(other, 1);
}
}

}

nodeCount = rooms + edges + 1;
graph = new double[nodeCount][nodeCount];

int newVertCounter = rooms;
for (int i = 0; i < rooms; i++) {
Map<Integer, Integer> doorCounts = roomsWithPanelsTo.get(i);

for (int other : doorCounts.keySet()) {
int nv = newVertCounter++;
graph[other][i] = doorCounts.get(other);
graph[i][nv] = Double.POSITIVE_INFINITY;
graph[nv][other] = Double.POSITIVE_INFINITY;
}
}

if (newVertCounter  != nodeCount - 1)
throw new AssertionError();

int source = newVertCounter;
for (int intrude : intruded) {
graph[source][intrude] = Double.POSITIVE_INFINITY;
}

double max = maxFlow(graph, source, panic);

if (Double.isInfinite(max))
System.out.println("PANIC ROOM BREACH");
else
System.out.printf("%d\n", (int) max);
}

public static double maxFlow(double[][] capacity,
int source, int sink) {
double[][] residual = new double[capacity.length][capacity.length];
double maxFlow = 0;

for (int i = 0; i < residual.length; i++) {
for (int j = 0; j < residual.length; j++) {
residual[i][j] = capacity[i][j];
}
}

// While there exists an augmenting path,
// increment the flow along this path.
int[] pred = bfs(residual, source);
while (pred[sink]  != -1) {
// Determine the amount by which we can increment the flow.
double increment = Double.POSITIVE_INFINITY;
for (int u = sink; pred[u]  != -2; u = pred[u]) {
increment = Math.min(increment, residual[pred[u]][u]);
}

for (int u = sink; pred[u]  != -2; u = pred[u]) {
residual[pred[u]][u] -= increment;
residual[u][pred[u]] += increment;
}
maxFlow += increment;
pred = bfs(residual, source);
}

return maxFlow;
}

public static int[] bfs (double[][] graph, int start) {

int[] pred = new int[graph.length];
for (int i = 0; i < pred.length; i++)
pred[i] = -1;

pred[start] = -2;

while (!q.isEmpty()) {
int u = q.remove();

for (int v = 0; v < graph.length; v++) {
if (pred[v] == -1 && graph[u][v] > 0) {
pred[v] = u;
}
}
}

return pred;
}
}
}
```