Description
Katu Puzzle is presented as a directed graph G(V,E) with each edge e(a,b) labeled by a boolean operator op (one of AND, OR, XOR) and an integer c (0≤c≤1). One Katu is solvable if one can find each vertex Vi a value Xi (0≤Xi≤1) such that for each edge e(a,b) labeled by op and c, the following formula holds:
XaopXb=c
The calculating rules are:
Given a Katu Puzzle, your task is to determine whether it is solvable.
Input
The first line contains two integers N (1≤N≤1000) and M,(0≤M≤1,000,000) indicating the number of vertices and edges.
The following M lines contain three integers a (0≤a<N), b(0≤b<N), c and an operator op each, describing the edges.
Output
Output a line containing “YES” or “NO”.
Samples
Input 复制
4 4
0 1 1 AND
1 2 1 OR
3 2 0 AND
3 0 0 XOR
Output
YES
Hint
X0=1,X1=1,X2=0,X3=1
思路：
算是2-SAT的板子题，所以思路偏重于建图的过程。
连边x->y表示选择x必须选择y，那么分别考虑以下的情况。
| a | b | a and b |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
所以当a and b = 0时：
- 若a=1,则必定满足b=0;
- 若b=1,则必定满足a=0;
当 a and b = 1时：
- a=1并且b=1;
| a | b | a or b |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
所以当 a or b = 0 时:
- a=0并且b=0;
当a or b = 1时：
- 若a=0,则b=1;
- 若b=0,则a=1；
| a | b | a xor b |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
所以当 a xor b = 0时：
- 若a=0，则b=0;
- 若b=0，则a=0;
- 若a=1，则b=1;
- 若b=1，则a=1;
当a xor b = 1时：
- 若a=0，则b=1;
- 若b=1,则a=0;
- 若a=1，则b=0;
- 若b=0，则a=1;
假设i表示该值取1，i+n表示该值取0。
按照以上列出的关系连边就可以。
这里有个要注意的点：当a=1并且b=1的时候如何连边？
这里的思路有点特殊：
add(a+n,a);add(b+n,b);
个人的理解是这样表示的含义是：
选择了a=0就必须选择a=1，所以只能选择a=1；
选择了b=0就必须选择b=1，所以只能选择b=1;
建图后跑一遍tarjan，如果发现i和i+n在同一个scc里，说明出现了矛盾。
如果所有的点都合法则输出YES。
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll,ll>PLL; typedef pair<int,int>PII; typedef pair<double,double>PDD; #define I_int ll inline ll read() { ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-')f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); } return x*f; } #define read read() #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) ll ksm(ll a,ll b,ll p) { ll res=1; while(b) { if(b&1)res=res*a%p; a=a*a%p; b>>=1; } return res; } const int maxn=1100,inf=0x3f3f3f3f; #define PI acos(-1) const double eps=1e-4; int n,m; vector<int>g[maxn]; void add(int x,int y) { g[x].push_back(y); } int dfn[maxn],low[maxn],timetmp; int id[maxn]; stack<int>stk; bool instk[maxn]; int cnt=0; void tarjan(int u) { dfn[u]=low[u]=++timetmp; stk.push(u); instk[u]=1; for(int t:g[u]) { if(!dfn[t]) { tarjan(t); low[u]=min(low[u],low[t]); } else if(instk[t]) low[u]=min(low[u],dfn[t]); } if(low[u]==dfn[u]) { int y; cnt ++ ; do { y=stk.top(); stk.pop(); instk[y]=0; id[y]=cnt; } while (y != u); } } int main() { n=read,m=read; while(m--) { char op[10]; int a=read,b=read,w=read; cin>>op; if(op[0]=='A') { if(w==0) { add(a,b+n);add(b,a+n); } else { /// ?add(a,1,b,1); add(a+n,a);add(b+n,b);///a+n为0,a为1 } } else if(op[0]=='O') { if(w==0) { ///add(a,0,b,0); add(a,a+n); add(b,b+n); } else {///a+n为0,a为1 add(a+n,b); add(b+n,a); } } else if(op[0]=='X') { if(w==1) { add(a+n,b); add(b,a+b); add(a,b+n); add(b+n,a); } else { add(a+n,b+n); add(b+n,a+n); add(a,b); add(b,a); } } } for(int i=0; i<2*n; i++) if(!dfn[i]) tarjan(i); for(int i=0; i<n; i++) if(id[i]==id[i+n]) { puts("NO"); return 0; } puts("YES"); return 0; }
![洛谷P2639-[USACO09OCT]Bessie‘s Weight Problem G（01背包）](https://ucc.alicdn.com/images/user-upload-01/20200726093842419.png?x-oss-process=image/resize,h_160,m_lfit)
![洛谷P2871-[USACO07DEC]Charm Bracelet S（01背包模板题）](https://ucc.alicdn.com/images/user-upload-01/20200725131735571.png?x-oss-process=image/resize,h_160,m_lfit)