题解 UVA10319 【Manhattan】

· · 题解

UVA10319 Manhattan解题报告：

更好地阅读体验

题意

分析

对于每一行$row_a$，套路地拆点：$row_a$表示向左，$rev_{row_a}$表示向右；同样的对于每一列$line_b$，$line_b$表示向上，$rev_{line_b}$表示向下。 然后，对于每一对起点终点$(a,b)\rightarrow(c,d)$，首先讨论不需要拐弯的特殊情况，即起点，终点处于同一行或同一列，这样我们直接强制确定某一行/列的方向就好了。 关于如何强制确定一个命题：**将这个命题的反命题向这个命题连边**，那么就一定无法选定这个命题的反命题了。 关于要拐弯的情况，以起点$(4,4)$终点$(1,2)$为例，我们需要保证以下命题成立： $$(row_4\cap line_2)\cup(line_4\cap row_1)=true$$ 意思就是第四行向左且第二列向上，或第四列向上且第一行向左。 这样我们就要想办法建出来图来满足这种形式的命题$(a\cap b)\cup(c\cap d)$： 有一个逻辑恒等式可以套上去： $$(a\cap b)\cup(c\cap d)=(a\cup c)\cap(a\cup d)\cap(b\cup c)\cap(b\cup d)$$ （读者自证不难） 这样，我们就可以按照上述式子建图了。 注意要对于$a,c$和$b,d$的大小关系分类讨论。 时间复杂度：$O(n\cdot m+k)

代码

记得有多组数据

#include<stdio.h>
const int maxn=30005,maxm=20005;
int s,a,m,n,e,top,flg,T;
int start[maxn],to[maxm],then[maxm],ans[maxn],stk[maxn],vis[maxn],rev[maxn],line[maxn],row[maxn];
inline void add(int x,int y){//加边
    then[++e]=start[x],start[x]=e,to[e]=y;
}
int dfs(int x){//dfs实现2-SAT
    if(vis[rev[x]])
        return 0;
    if(vis[x])
        return 1;
    vis[x]=1,stk[++top]=x;
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(dfs(y)==0)
            return 0;
    }
    return 1;
}
inline void addedge(int a,int b,int c,int d){//
    //(a and b)or(c and d)
    //=(a or c)and(a or d)and(b or c)and(b or d)
    add(rev[a],c),add(rev[c],a);
    add(rev[a],d),add(rev[d],a);
    add(rev[b],c),add(rev[c],b);
    add(rev[b],d),add(rev[d],b);
}
int main(){
    scanf("%d",&T);
    while(T--){
        e=top=flg=0;
        scanf("%d%d%d",&s,&a,&m);
        n=s+a;
        for(int i=1;i<=n;i++){
            rev[i]=n+i,rev[n+i]=i;
            start[i]=vis[i]=ans[i]=0;
            start[n+i]=vis[n+i]=ans[n+i]=0;
        }
        for(int i=1;i<=s;i++)
            row[i]=i;
        for(int i=1;i<=a;i++)
            line[i]=s+i;
        for(int i=1;i<=m;i++){
            //as for row:
            //a:<--------
            //rev[a]:--->
            //
            //as for line:
            //b:^ rev[b]:|
            //  |        |
            //  |        v
            int a,b,c,d;
            scanf("%d%d%d%d",&a,&b,&c,&d);
            if(a==c&&b==d)//起点，终点重合
                continue;
            a=row[a],b=line[b],c=row[c],d=line[d];//确定行，列
            if(a==c){//相同行
                if(b<d)
                    add(a,rev[a]);
                if(b>d)
                    add(rev[a],a);
            }
            if(b==d){//相同列
                if(a<c)
                    add(b,rev[b]);
                if(a>c)
                    add(rev[b],b);
            }
            if(a!=c&&b!=d){//普通情况
                //addedge(a,b,c,d):(a and b)or(c and d)
                if(a<c&&b<d)
                    addedge(rev[a],rev[d],rev[b],rev[c]);
                if(a<c&&b>d)
                    addedge(a,rev[d],rev[b],c);
                if(a>c&&b<d)
                    addedge(b,rev[c],rev[a],d);
                if(a>c&&b>d)
                    addedge(b,c,a,d);
            }
        }
        for(int i=1;i<=n;i++){//2-SAT
            top=0,ans[i]=0;
            if(dfs(i)==0){
                for(int j=1;j<=top;j++)
                    vis[stk[j]]=0;
                top=0,ans[i]=1;
                if(dfs(n+i)==0){
                    puts("No");
                    flg=1;
                    break;
                }
            }
        }
        if(flg==0)
            puts("Yes");
    }
    return 0;
}