首页 > 代码库 > BZOJ 1997: [Hnoi2010]Planar [2-SAT]

BZOJ 1997: [Hnoi2010]Planar [2-SAT]

2024-09-05 09:05:55   218人阅读

http://www.lydsy.com/JudgeOnline/problem.php?id=1997

题意：求一个有哈密顿回路的图是不是平面图。告诉哈密顿回路。

T<=100,3<=N<=200,M<=10000

 

哈密顿回路，所有点组成一个环，展开后不就和那道$poj$一样了......,避免相交只能一外一内

然后边数太多，平面图性质$m \le 3n-6$

并且还可以通过去掉环上的边来剪枝

然后注意人家输入的是环上的点不是点是环上哪个位置的点

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;const int N=2005,M=1e6+5,NN=1e4+5;typedef long long ll;inline int read(){    char c=getchar();int x=0,f=1;    while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}    while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();}    return x*f;}int n,m,v[N];struct Node{    int a,b;}p[NN];int tot;struct edge{    int v,ne;}e[M];int h[N],cnt=0;inline void ins(int u,int v){    cnt++;    e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt;}inline bool isIn(int i,int j){    return (p[i].a<p[j].a&&p[j].a<p[i].b&&p[i].b<p[j].b)||(p[j].a<p[i].a&&p[i].a<p[j].b&&p[j].b<p[i].b);}void buildGraph(){    for(int i=1;i<=m;i++)        for(int j=1;j<=m;j++) if(isIn(i,j)){            int x=i<<1,y=j<<1;            ins(x-1,y);ins(x,y-1);            ins(y-1,x);ins(y,x-1);        }}int dfn[N],low[N],dfc,belong[N],scc;int st[N],top;void dfs(int u){    dfn[u]=low[u]=++dfc;    st[++top]=u;    for(int i=h[u];i;i=e[i].ne){        int v=e[i].v;        if(!dfn[v]){            dfs(v);            low[u]=min(low[u],low[v]);        }else if(!belong[v])            low[u]=min(low[u],dfn[v]);    }    if(dfn[u]==low[u]){        scc++;int x=0;        while(x!=u){            x=st[top--];            belong[x]=scc;        }    }}bool judge(){    for(int i=1;i<=m;i++) if(belong[(i<<1)-1]==belong[i<<1]) return false;    return true;}int main(){    freopen("in","r",stdin);    int T=read();    while(T--){        cnt=0;memset(h,0,sizeof(h));        n=read();m=read();        for(int i=1;i<=m;i++) p[i].a=read(),p[i].b=read();        for(int i=1;i<=n;i++) v[read()]=i;        if(m>3*n-6) {puts("NO");continue;}        tot=0;        for(int i=1;i<=m;i++){            p[i].a=v[p[i].a],p[i].b=v[p[i].b];            if(p[i].a>p[i].b) swap(p[i].a,p[i].b);            if(p[i].b-p[i].a!=1&&(p[i].a!=1||p[i].b!=n)) p[++tot]=p[i];        }        m=tot;        buildGraph();        int _=m<<1;        for(int i=1;i<=_;i++) dfn[i]=low[i]=belong[i]=0;        for(int i=1;i<=_;i++) if(!dfn[i]) dfs(i);        if(judge()) puts("YES");        else puts("NO");    }}

 

 

 

BZOJ 1997: [Hnoi2010]Planar [2-SAT]


联系
我们