
ZOJ Problem Set  3579
Given n boolean variables and the result of m operations, calculate the maximum score you can get. The value of each variable only can be 0 or 1. The score is calculated by p rules. Each rule will be defined by five integers (i,x,j,y,w). It means that you can get w scores if the value of the ith variable equal to x and the value of the jth variable equal to y. Now, determine the value of each variable so that you can get the maximum score. InputThere are multiple test cases. The first line of each case contains three integer n m p( 1 ≤ n,m ≤ 100 , 1 ≤ p ≤ 5000 ). Then following m lines, each describe a result of an operation. The format of each line is : i [operation] j = x ( 1 ≤ i,j ≤ n , 0 ≤ x ≤ 1 ). It gives the result of the ith variable and the jth variable on the operation. There are only three kinds of operation("and","xor","or") in the data. The next p lines give the rules using format : i x j y w( 1 ≤ i,j ≤ n , 0 ≤ x,y ≤ 1 , 0 ≤ w ≤ 50 ). Process to the end of file. OutputOutput one line for each case. That is the maximum score you can get. I guarantee that there is at least one solution can satisfy the m operations. Sample Input3 2 2 1 xor 2 = 1 1 and 3 = 0 1 1 2 0 1 3 1 3 1 10 Sample Output10 Author: CHEN, Weijie Contest: ZOJ Monthly, February 2012 