| 题目名称 | 951. MAX-2-SAT |
|---|---|
| 输入输出 | max2sat.in/out |
| 难度等级 | ★★ |
| 时间限制 | 2000 ms (2 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cqw
于2012-07-22加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：0， 提交：24， 通过率：0% | ||||
 confoo |
90 | 3.673 s | 0.30 MiB | C++ |
 KZNS |
80 | 3.253 s | 0.29 MiB | C++ |
|
KZNS |
80 | 3.953 s | 0.29 MiB | C++ |
|
confoo |
70 | 4.942 s | 0.27 MiB | C++ |
|
KZNS |
60 | 4.414 s | 0.29 MiB | C++ |
|
KZNS |
60 | 4.563 s | 0.29 MiB | C++ |
|
confoo |
50 | 1.332 s | 0.31 MiB | C++ |
|
confoo |
40 | 0.536 s | 0.31 MiB | C++ |
|
confoo |
40 | 2.129 s | 0.31 MiB | C++ |
|
confoo |
40 | 6.444 s | 0.24 MiB | C++ |
| 本题关联比赛 | |||
| 20120722 | |||
| 20120722 | |||
| 关于 MAX-2-SAT 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
楼上是神犇，膜楼上
 NVIDIA
2016-11-07 15:57
3楼
| ||||
|
要有信仰！
蛤蛤祝福随机化！ PS：600轮随机化 90分应该已经是这题随机化做法的最好结果了…… $O(N^2T),T=600$ | ||||
|
并不能看懂……
 SPA
2016-02-19 09:32
1楼
| ||||
【问题描述】
在命题逻辑中，一个变量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（0<T<21）,表示测试数据的个数；
【输出格式】
对于每个测试数据，在一行输出值为真的字句的最大数目。
【样例】
max2sat.in
1
2 4
-2 1
2 1
2 -1
-1 -2
max2sat.out
3