M_sea

洛谷3209 [HNOI2010]平面图判定
LuoguBZOJ分析$\mathrm{2-SAT}$ 。首先把环抽出来,那么还会剩下很多边。考虑两条有交点的边(...
扫描右侧二维码阅读全文
03
2019/04

洛谷3209 [HNOI2010]平面图判定

Luogu

BZOJ

分析

$\mathrm{2-SAT}$ 。

首先把环抽出来,那么还会剩下很多边。

考虑两条有交点的边(这里的 $(1,4)$ 和 $(2,5)$ ):

img

显然只能一条不变(放在环里面),一条从外面绕一下(放在环外面)。

于是就可以上 $\mathrm{2-SAT}$ 了。对于两条有交点的边 $i$ 和 $j$ ,连以下 $4$ 条边:

  • $i\to j+m$ ,表示 $i$ 在里面 $j$ 就必须在外面。
  • $i+m\to j$ ,表示 $i$ 在外面 $j$ 就必须在里面。
  • $j\to i+m$ ,表示 $j$ 在里面 $i$ 就必须在外面。
  • $j+m\to i$ ,表示 $j$ 在外面 $i$ 就必须在里面。

然后跑 $\mathrm{tarjan}$ 缩点检查即可。

另外, $n$ 个点的平面图的边数最多为 $3n-6$ ,于是可以把边数降到 $O(n)$ 级别。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;

struct Edge { int v,nxt; } e[N];
int head[N],cnt=0;
int pos[N],x[N],y[N];

inline void addEdge(int u,int v) {
    e[++cnt]=(Edge){v,head[u]},head[u]=cnt;
}

int dfn[N],low[N],tim=0;
int bl[N],tot=0;
int sta[N],in[N],top=0;

inline void tarjan(int u) {
    dfn[u]=low[u]=++tim,sta[++top]=u,in[u]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
        else if (in[v]) low[u]=min(low[u],dfn[v]);
    }
    if (dfn[u]==low[u]) {
        ++tot;
        while (233) {
            int now=sta[top--];
            bl[now]=tot,in[now]=0;
            if (now==u) break;
        }
    }
}

int main() {
    int T=read();
    while (T--) {
        memset(head,0,sizeof(head)),cnt=0;
        memset(dfn,0,sizeof(dfn)),memset(low,0,sizeof(low)),tim=0;
        memset(bl,0,sizeof(bl)),tot=0;

        int n=read(),m=read(),tmp=0;
        for (re int i=1;i<=m;++i) x[i]=read(),y[i]=read();
        for (re int i=1;i<=n;++i) pos[read()]=i;
        if (m>3*n-6) { puts("NO"); continue; }
        for (re int i=1;i<=m;++i) x[i]=pos[x[i]],y[i]=pos[y[i]];
        
        for (re int i=1;i<=m;++i) {
            if (x[i]>y[i]) swap(x[i],y[i]);
            if (y[i]-x[i]==1) continue;
            ++tmp,x[tmp]=x[i],y[tmp]=y[i];
        }
        m=tmp;
        
        for (re int i=1;i<=m;++i)
            for (re int j=1;j<=m;++j)
                if (x[i]<x[j]&&x[j]<y[i]&&y[i]<y[j]) {
                    addEdge(i,j+n),addEdge(i+n,j);
                    addEdge(j,i+n),addEdge(j+n,i);
                }
        for (re int i=1;i<=m+m;++i)
            if (!dfn[i]) tarjan(i);

        int flag=1;
        for (re int i=1;i<=m;++i)
            if (bl[i]==bl[i+n]) { flag=0; break; }
        puts(flag?"YES":"NO");
    }
    return 0;
}
最后修改:2019 年 05 月 26 日 09 : 33 PM

4 条评论

  1. tiger0132

    并查集大法好(

    1. M_sea
      @tiger0132

      珂是我想学 2-sat

  2. smy

    %%%%%%%好神啊

    1. M_sea
      @smy

      Orz fake_magic_young!!!

发表评论