bzoj1997 [Hnoi2010]Planar

bzoj1997 [Hnoi2010]Planar

​​ 题目描述

若能将无向图G=(V,E)画在平面上使得任意两条无重合顶点的边不相交，则称G是平面图。判定一个图是否为平面图的问题是图论中的一个重要问题。现在假设你要判定的是一类特殊的图，图中存在一个包含所有顶点的环，即存在哈密顿回路。

输入输出格式

输入格式：

输入文件的第一行是一个正整数T，表示数据组数(每组数据描述一个需要判定的图)。接下来从输入文件第二行开始有T组数据，每组数据的第一行是用空格隔开的两个正整数N和M，分别表示对应图的顶点数和边数。紧接着的M行，每行是用空格隔开的两个正整数u和v（1<=u,v<=n），表示对应图的一条边(u,v),输入的数据保证所有边仅出现一次。每组数据的最后一行是用空格隔开的N个正整数，从左到右表示对应图中的一个哈密顿回路：V1,V2,…,VN，即对任意i≠j有Vi≠Vj且对任意1<=i<=n-1有(Vi,Vi-1) ∈E及(V1,Vn) ∈E。输入的数据保证100%的数据满足T<=100,3<=N<=200,M<=10000。

输出格式：

包含T行，若输入文件的第i组数据所对应图是平面图，则在第i行输出YES，否则在第i行输出NO，注意均为大写字母

输入输出样例

输入样例#1： 复制

2 6 9 1 4 1 5 1 6 2 4 2 5 2 6 3 4 3 5 3 6 1 4 2 5 3 6 5 5 1 2 2 3 3 4 4 5 5 1 1 2 3 4 5 输出样例#1： 复制

NO YES 说明

感谢@hibiki 对题目进行修正

又是细节没注意

注意：先把哈密顿路径标记出来 然后其他边不是在他里面就是在他外面 注意判断一下即可 如果有端点重叠就认定肯定不会有冲突 然后每个点拆开 建限制条件跑2-sat即可

注意 如果边数大于点数的三倍-6那么就一定不会是平面图了

所以直接puts(”NO”) 但是因为多组数据所以得把这些没用的信息读进来..

#include#include#include#includeusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if(T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int N=1300; const int M=1440000;struct node{ int y,next;}data[M];bool stackf[N];struct node1{int x,y;}edge[N>>1];int h[N],q[N],top,dfn[N],low[N],bl[N],num,s,b[N],id[N][2],n,m;inline void insert1(int x,int y){ data[++num].y=y;data[num].next=h[x];h[x]=num; data[++num].y=x;data[num].next=h[y];h[y]=num;}inline void tarjan(int x){ dfn[x]=low[x]=++num;stackf[x]=1;q[++top]=x; for (int i=h[x];i;i=data[i].next){ int y=data[i].y; if (!dfn[y]) tarjan(y),low[x]=min(low[x],low[y]); else if (stackf[y]) low[x]=min(low[x],dfn[y]); } if(low[x]==dfn[x]){ int y;++s; do{ y=q[top--];b[y]=s;stackf[y]=0; }while(y!=x); }}inline bool check(int i,int j){ int a1=edge[i].x,b1=edge[i].y,a2=edge[j].x,b2=edge[j].y; if (edge[i].x==edge[j].x||edge[i].x==edge[j].y||edge[i].y==edge[j].x||edge[i].y==edge[j].y) return 0; return (a23*n-6) { while(m--) read(),read(); while(n--) read();puts("NO");continue; } num=0;memset(h,0,sizeof(h));s=0; for (int i=1;i<=m;++i) edge[i].x=read(),edge[i].y=read(); for (int i=1;i<=n;++i) bl[read()]=i; for (int i=1;i<=m;++i){static int x,y; x=edge[i].x,y=edge[i].y; if(bl[x]>bl[y]) swap(x,y); edge[i].x=bl[x];edge[i].y=bl[y]; }memset(dfn,0,sizeof(dfn)); //for (int i=1;i<=m;++i) printf("%d %d\n",edge[i].x,edge[i].y); for (int i=1;i<=m;++i){ if(check1(i)) continue; for (int j=i+1;j<=m;++j){ if (check(i,j)) insert1(id[i][0],id[j][1]),insert1(id[i][1],id[j][0]); } } num=0;for (int i=1;i<=m<<1;++i) if (!dfn[i]) tarjan(i);bool flag=0; for (int i=1;i<=m;++i) if(!check1(i))if (b[id[i][0]]==b[id[i][1]]) {flag=1;puts("NO");break;} if (flag) continue;puts("YES"); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。