import java.io.*; import java.util.*; import java.awt.geom.*; /** * Solution to Job Postings. * * @author vanb */ public class jobpostings_vanb { public Scanner sc; public PrintStream ps; /** * A node of a max flow graph. */ public class Node { // Cost from the Source to this node public int cost = 100; // List of edges from this node public LinkedList edges = new LinkedList(); // The edge we got here from public Edge from = null; // For debugging public String name; // Is this node on the queue? public boolean onq; public Node( String name ) { this.name = name; } /** * Clear this node for a new graph */ public void clear() { cost = 0; edges.clear(); from = null; } } /** * An edge of a max flow graph. */ public class Edge { public Node destination; public int capacity; public int cost; public Edge dual; public Edge( Node d, int c, int s ) { capacity = c; cost = s; destination = d; dual = null; } } /** * Create a link between two nodes of a max flow graph. * * @param n1 From node * @param n2 To node * @param capacity Capacity from n1 to n2 * @param cost Cost to go from n1 to n2 */ public void link( Node n1, Node n2, int capacity, int cost ) { Edge e12 = new Edge( n2, capacity, cost ); Edge e21 = new Edge( n1, 0, -cost ); e12.dual = e21; e21.dual = e12; n1.edges.add( e12 ); n2.edges.add( e21 ); } public LinkedList queue = new LinkedList(); /** * Perform the Ford/Fulkerson algorithm on a graph. * * @param src Source node * @param snk Sink node * @param nodes The graph, represented as a list of nodes * @return The max flow from the source to the sink */ public int fordfulkerson( Node src, Node snk, List nodes ) { int total = 0; // Keep going until you can't get from the source to the sink for(;;) { // Reset the graph for( Node node : nodes ) { // Since the highest cost we'll ever get is 12, // 100 is, for all practical purposes, infinity. node.cost = 100; node.from = null; } src.cost = 0; queue.clear(); queue.add( src ); src.onq = true; while( !queue.isEmpty() ) { Node node = queue.removeFirst(); node.onq = false; for( Edge edge : node.edges ) { if( edge.capacity>0 && node.cost+edge.cost nodes = new LinkedList(); for(;;) { int n = sc.nextInt(); int m = sc.nextInt(); if( n==0 ) break; nodes.clear(); Node source = new Node( "Source" ); nodes.add( source ); Node sink = new Node( "Sink" ); nodes.add( sink ); // Create nodes for all of the available positions Node positions[][] = new Node[n][]; for( int i=0; i