Beauty of Array(模拟)
Time Limit:2000MS Memory Limit:32768KB 64bit IO Format:%lld & %llu
Description
SAT was the first known NP-complete problem. The problem remains NP-complete even if all expressions are written in conjunctive normal form with 3 variables per clause (3-CNF), yielding the 3-SAT problem. A K-SATproblem can be described as follows:
There are n persons, and m objects. Each person makes K wishes, for each of these wishes either he wants to take an object or he wants to reject an object. You have to take a subset of the objects such that every person is happy. A person is happy if at least one of his K wishes is kept. For example, there are 3 persons, 4 objects, and K = 2, and
Person 1 says, "take object 1 or reject 2."
Person 2 says, "take object 3 or 4."
Person 3 says, "reject object 3 or 1."
So, if we take object 1 2 3, then it is not a valid solution, since person 3 becomes unhappy. But if we take 1 2 4 then everyone becomes happy. If we take only 4, it's also a valid solution. Now you are given the information about the persons' wishes and the solution we are currently thinking. You have to say whether the solution is correct or not.
Input
Input starts with an integer T (≤ 100), denoting the number of test cases.
Each case starts with a line containing three integers n, m, K (1 ≤ n, m, K ≤ 30). Each of the next nlines contains K space separated integers where the ith line denotes the wishes of the ith person. Each of the integers in a line will be either positive or negative. Positive means the person wants the object in the solution; negative means the person doesn't want that in the solution. You can assume that the absolute value of each of the integers will lie between 1 and m.
The next line contains an integer p (0 ≤ p ≤ m) denoting the number of integers in the solution, followed byp space separated integers each between 1 and m, denoting the solution. That means the objects we have taken as solution set.
Output
For each case, print the case number and 'Yes' if the solution is valid or 'No' otherwise.
Sample Input
2
3 4 2
+1 -2
+3 +4
-3 -1
1 4
1 5 3
+1 -2 +4
2 2 5
Sample Output
Case 1: Yes
Case 2: No
题解:n个人找对象,对象从1--m,负数代表不要,正数代表要;现在给一组数,问是否满足所有人的意愿;
代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;
int mp[][]; int vis[];
int p;
int n, m, k;
set<int>st;
bool js(){
for(int i = ; i <= n; i++){
int flot = ;
for(int j = ; j <= k; j++){
if(st.count(mp[i][j])){
flot = ;
break;
}
}
if(!flot)return false;
}
return true;
}
int main(){
int T, kase = ;
scanf("%d", &T);
while(T--){
scanf("%d%d%d", &n, &m, &k);
for(int i = ; i <= n; i++){
for(int j = ; j <= k; j++){
scanf("%d", &mp[i][j]);
}
}
scanf("%d", &p);
st.clear();
memset(vis, , sizeof(vis));
int x;
for(int i = ; i <= p; i++){
scanf("%d", &x);
st.insert(x);
vis[x] = ;
}
for(int i = ; i<= m; i++){
if(!vis[i])st.insert(-i);
}
if(js())printf("Case %d: Yes\n", ++kase);
else
printf("Case %d: No\n", ++kase);
}
return ;
}
最新文章
- 【TextBox】重写右键菜单
- Gunicorn 问题
- 中国大学MOOC-陈越、何钦铭-数据结构-2016秋期中考试
- ubuntu14.04上安装Mysql-5.7.11
- BZOJ 2566 xmastree(树分治+multiset)
- 用 Graphviz 可视化函数调用
- [Exchange]2个不同域之间互发邮件
- 前台序列化传过来的值,后台获取之后封装到map当中,让后在转化成json格式,最后在把json里面的参数里面的某一个值进行分割,最后在存到json格式的数据中去。
- 预置第三方apk到MTK项目相关问题总结
- GMA Round 1 最短距离
- 第九节 java7JDK的常用封装类型
- spring session使用小记
- 初识Style和Theme
- laravel用crud修改产品items-新建resource controller和routing
- Oracle 聚合函数
- ftp 长传报错553 可能是选的目录不对
- (转)I 帧和 IDR 帧的区别
- .Net Core 使用EF Core方法
- virtulenv使用
- CF961D Pair Of Lines