MAX-2-SAT

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18: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