首页 > 代码库 > BZOJ 1997 Planar（2-SAT）

BZOJ 1997 Planar（2-SAT）

2024-07-09 00:08:56   219人阅读

题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=1997

题意：给出一个无向图。已知该图存在一个包含n个顶点的哈密顿回路。判定该图是不是平面图。

思路：圈将面分成内外两部分，则两条边同时在内部相交则同时在外部也是相交的。因此，必然是一个在内部一个在外部。据此建立2-SAT。平面图的边数小于等于三倍点数减六

 

int a[N],b[N],n,m,c[N];int d[N],f[N];vector<int> g[2000];void add(int u,int v){    g[u].pb(v);}int dfn[N],low[N],color[N],id,num,visit[N];stack<int> S;void DFS(int u){    dfn[u]=low[u]=++id;    S.push(u);        int i,v;    FOR0(i,SZ(g[u]))    {        v=g[u][i];        if(!dfn[v])        {            DFS(v);            upMin(low[u],low[v]);        }        else if(!visit[v])         {            upMin(low[u],dfn[v]);        }    }    if(low[u]==dfn[u])    {        num++;        do        {            v=S.top();            S.pop();            visit[v]=1;            color[v]=num;        }while(v!=u);    }} int ok(){    int i;    FOR1(i,m) if(color[i]==color[i+m]) return 0;    return 1;}int cross(int x1,int y1,int x2,int y2){     if(x1==x2||x1==y2||y1==x2||y1==y2) return 0;     x1=d[x1],y1=d[y1];     x2=d[x2],y2=d[y2];     if(x1>y1) swap(x1,y1);     return (x1<x2&&x2<y1)!=(x1<y2&&y2<y1);}int main(){    rush()    {        RD(n,m);        int i,j,x;        FOR1(i,m) RD(a[i],b[i]),f[i]=1;        FOR1(i,n) RD(c[i]),d[c[i]]=i;        if(m>3*n-6)        {            puts("NO");            continue;        }        FOR1(i,m)        {            x=abs(d[a[i]]-d[b[i]]);            if(x==1||x==n-1) f[i]=0;        }        int k=0;        FOR1(i,m) if(f[i]) a[++k]=a[i],b[k]=b[i];        m=k;        FOR0(i,2000) g[i].clear();        FOR1(i,m) for(j=i+1;j<=m;j++)        {            if(cross(a[i],b[i],a[j],b[j]))            {                add(i,j+m);                add(j,i+m);                add(i+m,j);                add(j+m,i);            }        }        clr(visit,0); clr(dfn,0); id=num=0;        FOR1(i,m+m) if(!visit[i]) DFS(i);        if(ok()) puts("YES");        else puts("NO");    }}

 

 

 


联系
我们