ZOJ Problem Set - 1639
You're going to design a multi-task operating system for an embedded system. Because the resources are limited on this mini computer, parallel running of some programs will probably give rise to the deadlock problem. According to experience, you have a list of programs that will hang up the system if all of them are running simultaneously. You are also given the priority of these programs. Now you're interested in the maximum value of the total priority of the programs that can run simultaneously in the system without hanging up.
The input has several test cases, each starts with n (2 <= n <= 16), the number of programs. The following n lines contain the name of the program and its priority, with each program on a line. The name is a string of no more than 10 characters. The priority is an integer from 1 to 100. The next line contains a single integer m (0 <= m <= 1,024), which is the length of the list of the conflicting programs. The following m lines each contains several names of the programs which cannot run together.
The input is terminated with a case n = 0. This case should not be processed.
Print the case number and the maximal total priority value you can get on a line. Adhere to the sample output format.
3 HARDDISK 20 FLOPPY 10 CDROM 15 1 CDROM HARDDISK 5 HARDDISK 20 FLOPPY 10 CDROM 15 SERIAL 25 MOUSE 20 3 CDROM HARDDISK FLOPPY FLOPPY SERIAL SERIAL MOUSE 0
System 1: 30 System 2: 60
Author: TANG, Jiqing
Source: Zhejiang University Local Contest 2003