MAX-2-SAT

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 是 关闭时间 2013年02月28日 星期四 23:02
输入文件 max2sat.in 输出文件 max2sat.out

【问题描述】

在命题逻辑中，一个变量pi的值可以为0（false），或者1(true)，一个文字lj可以是一个变量pi或变量的取反-pi。字句是文字的析取，而一个CNF公式则是字句的合取。当pi取值为1时，文字pi值为真，而当pi取值为0时，文字-pi值为真。如果一个字句中至少有一个文字值为真，则此字句值为真，而当一个CNF公式中所有字句值都为真时，此公式的值才为真。
一个CNF公式的MAX-SAT问题指的是如何为命题变量赋值，使得字句值为真的数目最多。这里因为所有的字句都只有两个文字，故称为MAX-2-SAT。
现在，请你来解决这个MAX-2-SAT问题。

【输入格式】

输入文件的第一行为一个正整数T

( 对于每个测试数据，第一行有两个整数N(1＜N＜31)和M(1＜M＜201)，N表示变量的个数，M为CNF公式中字句的个数。接下来有M个字句，每个字句包含两个整数x,y（-N<=x,y<=N）,其中正数代表取相对应的变量，而负数则代表取对应变量的反。

【输出格式】

  对于每个测试数据，在一行输出值为真的字句的最大数目。

【样例】

max2sat.in
1
2 4
-2 1
2 1
2 -1
-1 -2

max2sat.out
3