洛谷 P3209 [HNOI2010] 平面图判定

链接：

题意：

给出 \(T\) 张无向图 \((T\leq100)\)，并给出它对应的哈密顿回路，判断每张图是否是平面图。

分析：

平面图判定问题貌似是有线性做法的，这里给出链接，不是本题解重点。

在想不到上述算法的情况下，我们发现题目给出了该图的哈密顿回路，所以我们把无向图按哈密顿回路排成一个环。此时不在环上的边之间才可能出现交叉，所以我们考虑暴力 \(O(m^2)\) 枚举，对于可能产生交叉的两条边，只有他们在环的两侧时才不会相交，所以当 \(a,b\) 两条边可能相交时， \(a\) 在内侧则 \(b\) 一定在外侧。发现了 2-sat 模型。

算法：

简单说下算法，先找到所有不在环上的边。\(O(m^2)\) 暴力枚举，判断每两条边是否可能相交，如果可能相交，那么在 2-sat 中

  			insert(i,j+tot);

  			insert(i+tot,j);

  			insert(j,i+tot);

  			insert(j+tot,i);

最后 tarjan 求强连通分量，\(O(m+m^2)\)。

总复杂度 \(O(m^2)\)。

优化：

显然 \(O(m^2)\) 的复杂度无法通过 \(M\leq10000\) 的数据，但学过平面图的我们发现可以利用平面图的性质将 \(m\) 优化至 \(n\) 的范围。

有

  设G是一个面数为 f 的(n,m)连通简单平面图且n≥3,则m≤3n-6

我们可以特判 \(m\) 将 \(m\) 缩小到 \(3n-6\) 范围内，那么 \(O(n^2)\) 的时间复杂度就可以随便过了。

代码：

#include<bits/stdc++.h>

using namespace std;

#define in read()

inline int read(){

	int p=0,f=1;

	char c=getchar();

	while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}

	while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}

	return p*f;

}

const int N=1205;

const int M=360005;

int ed[N],tot;

struct edge{

	int v,next;

}e[M];

int head[N],en;

void insert(int u,int v){

	e[++en].v=v;

	e[en].next=head[u];

	head[u]=en;

}

int n,m;

int sta[N],low[N],dfn[N],id[N],sum,sign,top;

bool vis[N];

void dfs(int u){

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

	vis[u]=true;sta[++top]=u;

	for(int i=head[u];i;i=e[i].next){

		int v=e[i].v;

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

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

	}

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

		sum++;int i=sta[top--];

		while(i!=u){

			vis[i]=false;

			id[i]=sum;

			i=sta[top--];

		}

		vis[i]=false;

		id[i]=sum;

	}

}

int q[205];

int p[205];

bool check(){

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

		if(id[i]==id[i+tot])

			return false;

	return true;

}

struct QWQ{

	int a,b;

}a[10005];

void clean(){

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

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

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

	memset(sta,0,sizeof(sta));

	memset(id,0,sizeof(id));

	sum=sign=en=tot=top=0;

}

inline int cinab(int a,int b,int c){

	return (c>a&&c<b)?1:0;

}

signed main(){

	int T=in;

	while(T--){

		clean();

		n=in,m=in;

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

			a[i].a=in,a[i].b=in;

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

			q[i]=in;

			p[q[i]]=i;

			//p[i] 是 i 在环上的次序

		}

		if(m>3*n-6){

			cout<<"NO"<<'\n';

			continue;

		}

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

			a[i].a=p[a[i].a],a[i].b=p[a[i].b];

			if(a[i].a>a[i].b)

				swap(a[i].a,a[i].b);

			if(a[i].b-a[i].a!=1&&a[i].b-a[i].a!=n-1)

				ed[++tot]=i;

		}

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

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

				int xa=a[ed[i]].a,xb=a[ed[i]].b,ya=a[ed[j]].a,yb=a[ed[j]].b;

				//我们用一个端点在第一条线内而另一个端点不在来判断，需要特判端点相同的情况

				if(xa==ya||xa==yb||xb==ya||xb==yb)continue;

				if(cinab(xa,xb,ya)^cinab(xa,xb,yb)){

					insert(i,j+tot);

					insert(i+tot,j);

					insert(j,i+tot);

					insert(j+tot,i);

				}

			}

		for(int i=1;i<=tot*2;i++)if(!dfn[i])dfs(i);

		if(check())cout<<"YES"<<'\n';

		else cout<<"NO"<<'\n';

	}

	return 0;

}

巴特西

洛谷 P3209 [HNOI2010] 平面图判定

链接：

题意：

分析：

算法：

优化：

代码：

最新文章

热门文章