Panic Room

From Progteam

(Difference between revisions)
Jump to: navigation, search
(created)
 
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==
 +
<pre>
 +
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"))
 +
    intruded.add(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);
 +
    }
 +
}
 +
 +
roomsWithPanelsTo.add(doorCounts);
 +
    }   
 +
   
 +
    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;
 +
 
 +
    q.add(start);
 +
    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) {
 +
q.add(v);
 +
pred[v] = u;
 +
    }
 +
}
 +
    }
 +
 
 +
    return pred;
 +
}
 +
    }
 +
}
 +
</pre>
-
{{problem-stub}}
+
[[Category:Graph]]

Latest revision as of 02:37, 20 October 2008

Checkmark.jpg This problem has been solved by hjfreyer.



Panic Room
Problem Number 3084
Sorter: hjfreyer
Source: Unknown
Link: 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")) 
		    intruded.add(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);
		    }
		}
		
		roomsWithPanelsTo.add(doorCounts);
	    }    
	    
	    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;

	    q.add(start);
	    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) {
			q.add(v);
			pred[v] = u;
		    }
		}
	    }

	    return pred;
	}	
    }
}
Personal tools