正题
题目链接:http://poj.org/problem?id=3678
题目大意
n
n
n个
x
i
x_i
xi为
0
/
1
0/1
0/1。有
m
m
m个条件表示
x
i
a
n
d
x
j
=
a
x_i\ and\ x_j=a
xi and xj=a或
x
i
o
r
x
j
=
a
x_i\ or\ x_j=a
xi or xj=a或
x
i
x
o
r
x
j
=
a
x_i\ xor\ x_j=a
xi xor xj=a。 求构造一组合法的
x
i
x_i
xi。
解题思路
讨论一下
x
i
a
n
d
x
j
=
0
:
x_i\ and\ x_j=0:
xi and xj=0:
x
i
x_i
xi和
x
j
x_j
xj不都是
1
1
1，也就是
x
i
x_i
xi为
1
1
1那么
x
j
x_j
xj必须为0，反之
x
i
a
n
d
x
j
=
1
:
x_i\ and\ x_j=1:
xi and xj=1:
x
i
x_i
xi和
x
j
x_j
xj都是
1
1
1，这时候我们就构造矛盾条件
x
i
=
0
x_i=0
xi=0则
x
i
=
1
x_i=1
xi=1限制
x
i
=
0
x_i=0
xi=0即可，
x
j
x_j
xj同
x
i
o
r
x
j
=
0
:
x_i\ or\ x_j=0:
xi or xj=0:
x
i
x_i
xi和
x
j
x_j
xj都是
0
0
0，和上面
2
2
2一样构造即可
x
i
o
r
x
j
=
1
:
x_i\ or\ x_j=1:
xi or xj=1:
x
i
x_i
xi和
x
j
x_j
xj不都是
0
0
0，和上面
1
1
1一样构造即可
x
i
x
o
r
x
j
=
0
:
x_i\ xor\ x_j=0:
xi xor xj=0:那么
x
i
=
0
⇒
x
j
=
0
x_i=0\Rightarrow x_j=0
xi=0⇒xj=0且
x
i
=
1
⇒
x
j
=
1
x_i=1\Rightarrow x_j=1
xi=1⇒xj=1，反之
x
i
x
o
r
x
j
=
1
:
x_i\ xor\ x_j=1:
xi xor xj=1:那么
x
i
=
0
⇒
x
j
=
1
x_i=0\Rightarrow x_j=1
xi=0⇒xj=1且
x
i
=
1
⇒
x
j
=
0
x_i=1\Rightarrow x_j=0
xi=1⇒xj=0，反之
时间复杂度
O
(
n
)
O(n)
O(n)
c
o
d
e
code
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std
;
const int N
=2100;
struct node
{
int to
,next
;
}a
[N
*4000];
int n
,m
,tot
,num
,cnt
,ls
[N
];
int dfn
[N
],low
[N
],color
[N
];
bool ins
[N
];
stack
<int> S
;
void addl(int x
,int y
){
a
[++tot
].to
=y
;
a
[tot
].next
=ls
[x
];
ls
[x
]=tot
;
return;
}
void tarjan(int x
){
dfn
[x
]=low
[x
]=++cnt
;
ins
[x
]=1;S
.push(x
);
for(int i
=ls
[x
];i
;i
=a
[i
].next
){
int y
=a
[i
].to
;
if(!dfn
[y
])tarjan(y
),low
[x
]=min(low
[x
],low
[y
]);
else if(ins
[y
])low
[x
]=min(low
[x
],dfn
[y
]);
}
if(dfn
[x
]==low
[x
]){
++num
;
while(S
.top()!=x
){
color
[S
.top()]=num
;
ins
[S
.top()]=0;
S
.pop();
}
color
[S
.top()]=num
;
ins
[S
.top()]=0;
S
.pop();
}
return;
}
int main()
{
scanf("%d%d",&n
,&m
);
for(int i
=1;i
<=m
;i
++){
int a
,b
,w
;char op
[4];
scanf("%d %d %d %s",&a
,&b
,&w
,op
);
if(op
[0]=='A'){
if(w
)addl(a
,a
+n
),addl(b
,b
+n
);
else addl(b
+n
,a
),addl(a
+n
,b
);
}
if(op
[0]=='O'){
if(w
)addl(b
,a
+n
),addl(a
,b
+n
);
else addl(a
+n
,a
),addl(b
+n
,b
);
}
if(op
[0]=='X'){
if(w
)addl(a
,b
+n
),addl(b
,a
+n
),addl(a
+n
,b
),addl(b
+n
,a
);
else addl(a
,b
),addl(b
,a
),addl(a
+n
,b
+n
),addl(b
+n
,a
+n
);
}
}
for(int i
=0;i
<2*n
;i
++)
if(!dfn
[i
])tarjan(i
);
for(int i
=0;i
<n
;i
++)
if(color
[i
]==color
[i
+n
])
{printf("NO\n");return 0;}
printf("YES\n");return 0;
}
