Panic Room

From Progteam

Revision as of 02:37, 20 October 2008 by Hjfreyer (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
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