// David Poeschl // Fail to get augmenting paths due to incorrect capacity check import java.util.*; public class WaifDavidWrong2 { private static int numChildren; private static int numToys; private static int numGroups; private static int numNodes; private static int[][] flow; private static int[][] capacity; public static void main(String[] args) { Scanner scan = new Scanner(System.in); numChildren = scan.nextInt(); numToys = scan.nextInt(); numGroups = scan.nextInt(); numNodes = 1 + numChildren + numToys + numGroups + 1; flow = new int[numNodes][numNodes]; capacity = new int[numNodes][numNodes]; createCapacityMatrix(scan); fillFlowMatrix(); printResult(); scan.close(); } private static void createCapacityMatrix(Scanner scan) { // Connect source {0} to all children [1, numChildren] for (int i = 1; i <= numChildren; i++) capacity[0][i] = capacity[i][0] = 1; // Connect children [1, numChildren] to toys [numChildren + 1, numChildren + numToys] for (int i = 1; i <= numChildren; i++) { int numAcceptableToys = scan.nextInt(); for (int j = 0; j < numAcceptableToys; j++) { int toyNumber = scan.nextInt(); int toyIndex = numChildren + toyNumber; capacity[i][toyIndex] = 1; } } // Connect toys [numChildren + 1, numChildren + numToys] to groups [numChildren + numToys + 1, numChildren + numToys + numGroups]; // Connect groups [numChildren + numToys + 1, numChildren + numToys + numGroups] to the sink {numNodes -1} List groupedToys = new ArrayList(); for (int i = 1; i <= numGroups; i++) { int groupIndex = numChildren + numToys + i; int numToysInGroup = scan.nextInt(); for (int j = 0; j < numToysInGroup; j++) { int toyNumber = scan.nextInt(); int toyIndex = numChildren + toyNumber; capacity[toyIndex][groupIndex] = capacity[groupIndex][toyIndex] = 1; groupedToys.add(toyNumber); } capacity[groupIndex][numNodes - 1] = capacity[numNodes - 1][groupIndex] = scan.nextInt(); } // Connect groupless toys (some elements of [numChildren + 1, numChildren + numToys]) to the sink {numNodes - 1} for (int i = 1; i <= numToys; i++) if (!groupedToys.contains(i)) capacity[numChildren + i][numNodes - 1] = capacity[numNodes - 1][numChildren + i] = 1; } private static void fillFlowMatrix() { while (true) { AugmentingPath path = getAugmentingPath(); if (path.additionalPathCapacity == 0) break; int currentNode = numNodes - 1; while (currentNode != 0) { int previousNode = path.predecessors[currentNode]; flow[previousNode][currentNode] += path.additionalPathCapacity; flow[currentNode][previousNode] -= path.additionalPathCapacity; currentNode = previousNode; } } } private static AugmentingPath getAugmentingPath() { AugmentingPath path = new AugmentingPath(); int[] pathCapacityToNode = new int[numNodes]; pathCapacityToNode[0] = 1000000; Queue nodesToVisit = new LinkedList(); nodesToVisit.add(0); while (nodesToVisit.size() > 0) { int node = nodesToVisit.remove(); for (int nextNode = 0; nextNode < numNodes; nextNode++) { if (capacity[node][nextNode] != 0 && path.predecessors[nextNode] == -1 && capacity[node][nextNode] - flow[node][nextNode] > 0) { path.predecessors[nextNode] = node; pathCapacityToNode[nextNode] = Math.min(pathCapacityToNode[node], capacity[node][nextNode] - flow[node][nextNode]); if (nextNode == numNodes - 1) { path.additionalPathCapacity = pathCapacityToNode[nextNode]; return path; } else { nodesToVisit.add(nextNode); } } } } return path; } private static void printResult() { int total = 0; for (int i = 0; i < numNodes; i++) total += flow[i][numNodes - 1]; System.out.println(total); } private static class AugmentingPath { int additionalPathCapacity; int[] predecessors; public AugmentingPath() { predecessors = new int[numNodes]; Arrays.fill(predecessors, -1); predecessors[0] = -2; } } }