Panic Room

(Difference between revisions)
 Revision as of 17:11, 27 February 2007 (view source)EditBot (Talk | contribs) (created)← Older edit Latest revision as of 02:37, 20 October 2008 (view source)Hjfreyer (Talk | contribs) Line 1: Line 1: + {{solved|hjfreyer}} + {{problem {{problem |name=Panic Room |name=Panic Room |number=3084 |number=3084 - |difficulty + |sorter=hjfreyer |type |type |source |source }} }} '''Panic Room''' is problem number 3084 on the Peking University ACM '''Panic Room''' is problem number 3084 on the Peking University ACM - site. + 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 intruded = new HashSet();
+
+                                                                                      double[][] graph;
+                                                                                      int nodeCount;
+
+                                                                                      public Instance() {
+                                                                                      rooms = in.nextInt();
+                                                                                      panic = in.nextInt();
+
+                                                                                      List> roomsWithPanelsTo =
+                                                                                      new ArrayList>();
+
+                                                                                      int edges = 0;
+
+                                                                                      for (int i = 0; i < rooms; i++) {
+                                                                                      if (in.next().equals("I"))
+
+                                                                                      Map doorCounts =
+                                                                                      new HashMap();
+
+                                                                                      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 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) {
+                                                                                      Queue q = new LinkedList();
+
+                                                                                      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;
+                                                                                      }
+                                                                                      }
+                                                                                      }
+
- {{problem-stub}} + [[Category:Graph]]

Latest revision as of 02:37, 20 October 2008

 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) {
Queue<Integer> q = new LinkedList<Integer>();

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;
}
}
}
```