bzoj1997 [HNOI2010]平面图判定Planar

链接

bzoj

luogu

思路

好像有很多种方法过去。我只说2-sat

环上的边，要不在里面，要不在外边。

有的边是不能同时在里面的,可以O(m^2)的连边

但是m是10000，不过平面图内边数不得超过3*n-6,

m太大的直接NO就好了，其他的n,m是一个数量级的，直接2-sat暴力连边做就好了。

细节

双向边

是边m进行2-sat，不是点n

代码

#include <bits/stdc++.h>

using namespace std;

const int N=1207;

int read() {

    int x=0,f=1;char s=getchar();

    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;

    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';

    return x*f;

}

int n,m,a[N],u[10005],v[10005],tong[N],rk[10005];

struct node {int v,nxt;}e[N*N*2];

int head[N],tot;

map<pair<int,int >,int > Hash;

void add(int u,int v) {

    e[++tot].v=v;

    e[tot].nxt=head[u];

    head[u]=tot;

}

int low[N],dfn[N],cnt,stak[N],top,vis[N],col,belong[N];

void tarjan(int u) {

    dfn[u]=low[u]=++cnt;

    vis[u]=1;

    stak[++top]=u;

    for(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(vis[v]) {

            low[u]=min(low[u],dfn[v]);

        }

    }

    if(low[u]==dfn[u]) {

        ++col;

        while(stak[top]!=u) {

            vis[stak[top]]=0;

            belong[stak[top]]=col;

            top--;

        }

        vis[u]=0;

        belong[u]=col;

        top--;

    }

}

void clear() {

    tot=cnt=col=0;

    Hash.clear();

    memset(head,0,sizeof(head));

    memset(low,0,sizeof(low));

    memset(dfn,0,sizeof(dfn));

    memset(rk,0,sizeof(rk));

}

void solve() {

    clear();

    n=read(),m=read();

    for(int i=1;i<=m;++i) u[i]=read(),v[i]=read();

    for(int i=1;i<=n;++i) a[i]=read();

    for(int i=2;i<=n;++i) {

        rk[a[i]]=i;

        Hash[make_pair(a[i],a[i-1])]=1;

        Hash[make_pair(a[i-1],a[i])]=1;

    }

    Hash[make_pair(a[1],a[n])]=1;

    Hash[make_pair(a[n],a[1])]=1;

    if(m>3*n-6) return puts("NO"),void();

    for(int i=1;i<=m;++i) {

        if(!Hash[make_pair(u[i],v[i])]) {

            memset(tong,0,sizeof(tong));

            for(int j=1,flag=0;j<=n;++j) {

                if(u[i]==a[j]||v[i]==a[j]) flag=flag^1;

                tong[j]=flag;

            }

            for(int j=i+1;j<=m;++j) {

                if(Hash[make_pair(u[j],v[j])]) continue;

                if(u[i]==v[j]||u[i]==u[j]||v[i]==v[j]||v[i]==u[j]) continue;

                if(tong[rk[u[j]]]^tong[rk[v[j]]]) {

                    add(i,j+m);

                    add(j+m,i);

                    add(i+m,j);

                    add(j,i+m);

                }

            }

        }

    }

    for(int i=1;i<=2*m;++i)

        if(!dfn[i])

            tarjan(i);

    for(int i=1;i<=m;++i)

        if(belong[i]==belong[i+m])

            return puts("NO"),void();

    return puts("YES"),void();

}

int main() {

    for(int T=read();T;T--) solve();

    return 0;

}