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 i-th variable equal to x and the value of the j-th variable equal to y. Now, determine the value of each variable so that you can get the maximum score.
There 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 i-th variable and the j-th 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.
Output 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.
3 2 2 1 xor 2 = 1 1 and 3 = 0 1 1 2 0 1 3 1 3 1 10
Author: CHEN, Weijie
Contest: ZOJ Monthly, February 2012