php mysql开发网站开发,网站宣传推广策划方案,装修公司加盟免费,做网站公司属于什么行业活动 - AcWing
给定 n 个还未赋值的布尔变量 x1∼xn。
现在有 m 个条件#xff0c;每个条件的形式为 “xi 为 0/1 或 xj 为 0/1 至少有一项成立”#xff0c;例如 “x1 为 1 或 x3 为 0”、“x8 为 0 或 x4 为 0” 等。
现在#xff0c;请你对这 n 个布尔变量进行赋值每个条件的形式为 “xi 为 0/1 或 xj 为 0/1 至少有一项成立”例如 “x1 为 1 或 x3 为 0”、“x8 为 0 或 x4 为 0” 等。
现在请你对这 n 个布尔变量进行赋值0 或 1使得所有 m 个条件能够成立。
输入格式
第一行包含两个整数 n,m。
接下来 m 行每行包含四个整数 i,a,j,b用来描述一个条件表示 “xi 为 a 或 xj 为 b”。
输出格式
如果问题有解则第一行输出 POSSIBLE第二行输出 n 个整数表示赋值后的 n 个变量 x1∼xn 的值0 或 1整数之间用单个空格隔开。
如果问题无解则输出一行 IMPOSSIBLE 即可。
如果答案不唯一则输出任意一种正确答案即可。
数据范围
1≤n,m≤106, 1≤i,j≤n, 0≤a,b≤1
输入样例
3 2
1 1 3 1
2 0 3 0输出样例
POSSIBLE
1 1 0
解析
该文件无法打开 - AcWing 本题是 2-SAT 问题的模板题对于每个条件 a∧b得出推导公式 −a→b 和 −b→a按照推导公式建图然后求强连通分量并进行缩点如果任意一个变量的两种取值在同一个强连通分量中说明无解。否则枚举每个变量选取所在强连通分量拓扑序靠后的取值。
#includeiostream
#includestring
#includecstring
#includecmath
#includectime
#includealgorithm
#includeutility
#includestack
#includequeue
#includevector
#includeset
#includemath.h
#includemap
#includesstream
#includedeque
#includeunordered_map
#includeunordered_set
#includebitset
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pairint, int PII;
const int N 2e610, M 2e6 10, INF 0x3f3f3f3f;
int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], ts;
int stk[N], top;
bool in_stk[N];
int id[N],cnt;void add(int a, int b) {e[idx] b, ne[idx] h[a], h[a] idx;
}int tarjan(int u) {dfn[u] low[u] ts;stk[top] u, in_stk[u] 1;for (int i h[u]; i ! -1; i ne[i]) {int j e[i];if (!dfn[j]) {tarjan(j);low[u] min(low[u], low[j]);}else if (in_stk[j]) {low[u] min(low[u], dfn[j]);}}if (dfn[u] low[u]) {int y;cnt;do {y stk[top--];in_stk[y] 0;id[y] cnt;} while (y ! u);}
}int main() {cin n m;memset(h, -1, sizeof h);for (int i 1,x,a,y,b; i m; i) {scanf(%d%d%d%d, x, a, y, b);x--, y -- ;add(2 * x !a, 2 * y b);add(2 * y !b, 2 * x a);}for (int i 0; i 2 * n; i) {if (!dfn[i])tarjan(i);}for (int i 0; i n; i) {if (id[i * 2] id[2 * i 1]) {cout IMPOSSIBLE endl;return 0;}}cout POSSIBLE endl;for (int i 0; i n; i) {if (id[i * 2] id[i * 2 1])printf(0 );else printf(1 );}return 0;
}
