题解 UVA10319 【Manhattan】

这道题虽然很难看出来，但是确是一道2-SAT的题目。怎么进行2-SAT呢？因为一条路如果是南北走向的要么向南，要么向北，东西走向也一样。所以可以用偶数位来存是否向南或者向东，奇数位存向北或者向东。 代码如下 ```cpp #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int T,n,m,q,cnt,p; int f[4000],s[4000];//偶数：南+东，奇数：北+西 int head[4000],nxt[4000],to[4000]; void addedge(int x,int y) { cnt++; nxt[cnt]=head[x]; head[x]=cnt; to[cnt]=y; } bool dfs(int x) { if(f[x]) return 1; if(f[x^1]) return 0; f[x]=1; s[++p]=x; for(int i=head[x];i!=-1;i=nxt[i]) if(!dfs(to[i])) return 0; return 1; } bool judge() { for(int i=0;i<2*(n+m);i+=2) { if(!f[i] && !f[i^1]) { p=0; if(!dfs(i)) { while(p>0) f[s[p--]]=0; if(!dfs(i^1)) return 0; } } } return 1; } int main() { scanf("%d",&T); while(T--) { cnt=0,p=0; memset(f,0,sizeof(f)); memset(head,-1,sizeof(head)); scanf("%d%d%d",&n,&m,&q); for(int i=1;i<=q;i++) { int s1,a1,s2,a2; scanf("%d%d%d%d",&s1,&a1,&s2,&a2); s1--,a1--,s2--,a2--; if(s1==s2 && a1==a2) continue; a1+=n,a2+=n; if(s1==s2) addedge((s1*2+(a1<a2))^1,s2*2+(a1<a2)),addedge((s2*2+(a1<a2))^1,s1*2+(a1<a2)); else if(a1==a2) addedge((a1*2+(s1<s2))^1,a2*2+(s1<s2)),addedge((a2*2+(s1<s2))^1,a1*2+(s1<s2)); else { addedge((s1*2+(a1<a2))^1,s2*2+(a1<a2)),addedge((s2*2+(a1<a2))^1,s1*2+(a1<a2)); addedge((s1*2+(a1<a2))^1,a1*2+(s1<s2)),addedge((a1*2+(s1<s2))^1,s1*2+(a1<a2)); addedge((a2*2+(s1<s2))^1,a1*2+(s1<s2)),addedge((a1*2+(s1<s2))^1,a2*2+(s1<s2)); addedge((s2*2+(a1<a2))^1,a2*2+(s1<s2)),addedge((a2*2+(s1<s2))^1,s2*2+(a1<a2)); } } if(judge()) printf("Yes\n"); else printf("No\n"); } return 0; } ```