题解 UVA10319 【Manhattan】

2018-05-08 21:14:47


这道题虽然很难看出来,但是确是一道2-SAT的题目。怎么进行2-SAT呢?因为一条路如果是南北走向的要么向南,要么向北,东西走向也一样。所以可以用偶数位来存是否向南或者向东,奇数位存向北或者向东。

代码如下

#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;
}