UVA10319 Manhattan解题报告

解题报告

---

UVA10319 Manhattan解题报告：

更好地阅读体验

题意

• 一个$n\times m$的矩阵，每一行和每一列必须选定一个方向，只能沿着这个方向走；
• 给定$k$对起点与终点，询问是否有一种方向选定方案使得每一对起点走到终点最多只需要拐一次弯。
• $1\leqslant n,m\leqslant 30,1\leqslant k\leqslant 200$。

分析

$\text{2-SAT}$神仙题。

对于每一行$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;
}