思路：裸的2-SAT。
#include<map> #include<set> #include<cmath> #include<queue> #include<cstdio> #include<vector> #include<string> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define Maxn 2010 #define Maxm 100010 #define LL __int64 #define Abs(x) ((x)>0?(x):(-x)) #define lson(x) (x<<1) #define rson(x) (x<<1|1) #define inf 0x7fffffff #define Mod 1000000007 using namespace std; int dfn[Maxn],low[Maxn],id[Maxn],Stack[Maxn],lab,num,e,top,vi[Maxn],n,m; vector<int> head[Maxn]; void init() { memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); lab=num=top=0; memset(vi,0,sizeof(vi)); memset(id,0,sizeof(id)); for(int i=0;i<=2*n;i++) head[i].clear(); } void Tarjan(int u) { int i,v,sz; dfn[u]=low[u]=++lab; Stack[top++]=u; vi[u]=1; sz=head[u].size(); for(i=0;i<sz;i++){ v=head[u][i]; if(!dfn[v]){ Tarjan(v); low[u]=min(low[v],low[u]); } if(vi[v]) low[u]=min(low[u],dfn[v]); } if(low[u]==dfn[u]){ ++num; do{ i=Stack[--top]; id[i]=num; vi[i]=0; }while(i!=u); } return ; } int main() { int i,j,a,b,c,d; while(scanf("%d",&n)!=EOF){ init(); scanf("%d",&m); for(i=1;i<=m;i++){ scanf("%d%d%d%d",&a,&b,&c,&d); a++; b++; if(c==0&&d==0) head[a].push_back(b+n),head[b].push_back(a+n); if(c==0&&d==1) head[a].push_back(b),head[b+n].push_back(a+n); if(c==1&&d==0) head[a+n].push_back(b+n),head[b].push_back(a); if(c==1&&d==1) head[a+n].push_back(b),head[b+n].push_back(a); } for(i=1;i<=2*n;i++){ if(!dfn[i]) Tarjan(i); } for(i=1;i<=n;i++) if(id[i]==id[i+n]) break; if(i<=n) printf("NO "); else printf("YES "); } return 0; }