1. 

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS10/11
* Problem: 259 Software Allocation
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=4&page=show_problem&problem=195
*
* @author Fabian Liebl
* @version 1.0, 10/06/2010
*
* Method : max-flow
* Status : Accepted
* Runtime: 0.644
*/

import java.io.*;
import java.util.LinkedList;

public class Main {

private static int s,t; // Start and target node
private static int[][] C; // Capacities
private static int[][] E; // Neighbours
private static int[][] F; // Flow matrix

// For Breadth-First-Search
private static int[] M;
private static int[] P;

private static void breadthFirstSearch() {
int u,v;

LinkedList<Integer> queue = new LinkedList<Integer>();

P[0] = -2; // No backjumping to source
for (u = 1; u < t+1; u++) {
P[u] = -1; // Set all to unvisited
}
M[0] = Integer.MAX_VALUE;
queue.clear();
queue.addLast(s);
while (queue.size() > 0) {
u = queue.removeFirst();
for (int i = 0; i < E[u].length; i++) {
v = E[u][i];
if ((C[u][v] - F[u][v] > 0) && (P[v] == -1)) {
P[v] = u;
M[v] = Math.min(M[u], C[u][v] - F[u][v]);
if (v == t) {
return;
} else {
queue.addLast(v);
}
}
}
}
// No path found
M[t] = 0;
}

public static void main(String[] args) throws IOException {
BufferedReader inputReader = new BufferedReader(new InputStreamReader(System.in));

int f; // Flow value
int neededF; // Needed flow
int v,u; // Indices
int firstComp; // First computer in matrix
char[] jobName; // Job names
char[] output = new char[10];

LinkedList<String> input = new LinkedList<String>();
String line = " ";
String[] job;

while (line != null) {
input.clear();
line = inputReader.readLine();
while ((line != null) && (!line.equals(""))) {
// Check line format
if (line.matches("[ABCDEFGHIJKLMNOPQRSTUVWXYZ][123456789] [0123456789]+;")) {
input.add(line);
}
line = inputReader.readLine();
}

if (input.size() == 0) {
return;
}

// Build Graph
s = 0;
t = 11 + input.size();
C = new int[t+1][t+1];
E = new int[t][];
f = 0;
neededF = 0;
F = new int[t+1][t+1];
M = new int[t+1];
P = new int[t+1];

// s has connections to the jobs
E[s] = new int[input.size()];
jobName = new char[input.size()];
// Jobs have connections to the Computers and back to s
u = 1;
firstComp = 1 + input.size(); // First computer
for(String app: input) {
job = app.split(" ");
jobName[u-1] = job[0].charAt(0);
// Add connection from s to here
E[s][u-1] = u;
// Add capacity for this connection
C[s][u] = Integer.parseInt(job[0].charAt(1) + "");
neededF += Integer.parseInt(job[0].charAt(1) + "");
// Add connections to computers and to s
E[u] = new int[job[1].length() + 1];
E[u][0] = s;
for (int i = 0; i < job[1].length() - 1; i++) {
v = firstComp + Integer.parseInt(job[1].charAt(i) + "");
E[u][i+1] = v;
// Add capacity
C[u][v] = 1;
// Use F temporarily to save incoming connections to computers
F[v][0] ++;
}
u++;
}
// Computers have connections to t and to incoming problems
for (int i = firstComp; i < firstComp + 10; i++) {
E[i] = new int[F[i][0] + 1];
E[i][0] = t;
C[i][t] = 1;
u = 1;
// Go through jobs
for (int j = 1; j < input.size() + 1; j++) {
for (v = 0; v < E[j].length; v++) {
if (E[j][v] == i) {
E[i][u] = j;
u++;
}
}
}
// Clear the temporary value stored in F
F[i][0] = 0;
}
// t has no connections

while (true) {
// Find path through breadth first search
breadthFirstSearch();

if (M[t] == 0) {
break;
}
f += M[t];
// Path is in P (backwards)
v = t;
while (v != s) {
u = P[v];
// Add flow
F[u][v] += M[t];
// Add negative flow in the other direction
F[v][u] -= M[t];
v = u;
}
}

if (f < neededF) {
System.out.println("!");
} else {
for (int i = 0; i < output.length; i++) {
output[i] = '_';
}
for (int i = 1; i < input.size() + 1; i++) {
for (int j = firstComp; j < firstComp + 10; j++) {
if (F[i][j] > 0) {
output[j - firstComp] = jobName[i-1];
}
}
}
System.out.printf("%c%c%c%c%c%c%c%c%c%c\n", output[0], output[1],
output[2], output[3], output[4], output[5], output[6], output[7], output[8], output[9]);
}
}
}

}