【HNOI2010】平面图判定 – 徐亦轲的博客

继续刷。。【写完这个题解还是复习一下的好

首先我们把哈密顿回路展成一个圆。。那么其他的边就是圆上的弧

如果弧相互交叉了我们可以将其中一个翻到外面去。。但是不能同时翻两个

于是在相互交叉的弧之间连边然后黑白染色即可。。

发现边数最大有10000。。

但是伟大的欧拉告诉我们平面图中m<=3n-6

特判掉不符合的，所以边数最多只有594条了。。

// <planar.cpp> - 02/27/16 04:07:33
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int getint(){
	int res=0,fh=1;char ch=getchar();
	while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
	if(ch=='-')fh=-1,ch=getchar();
	while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
	return fh*res;
}
pair <int,int> e[10001];
int hmd[201],c[600];
vector <int> b[600];
bool xj(int x,int y){
	int a1=hmd[e[x].first],b1=hmd[e[x].second],a2=hmd[e[y].first],b2=hmd[e[y].second];
	if(a1==a2||a1==b2||a2==b1||b1==b2)return 0;
	return (a1>a2&&a1<b2)^(b1>a2&&b1<b2);
}
bool color(int x){
	for(int i=0;i<b[x].size();i++){
		int next=b[x][i];
		if(!c[next]){
			c[next]=-c[x];
			if(!color(next))return 0;
		}else if(c[next]==c[x])return 0;
	}
	return 1;
}
int main(){
	int T=getint();
	while(T--){
		int n=getint(),m=getint();
		for(int i=1;i<=m;i++)e[i]=make_pair(getint(),getint());
		for(int i=1;i<=n;i++)hmd[getint()]=i;
		if(m>3*n-6){printf("NO\n");continue;}
		for(int i=1;i<=m;i++)
			if(hmd[e[i].first]>hmd[e[i].second])swap(e[i].first,e[i].second);
		for(int i=1;i<=m;i++)b[i].clear();
		for(int i=1;i<=m;i++){
			if(hmd[e[i].second]-hmd[e[i].first]==1||hmd[e[i].second]-hmd[e[i].first]==n-1)continue;
			for(int j=1;j<=m;j++){
				if(hmd[e[j].second]-hmd[e[j].first]==1||hmd[e[j].second]-hmd[e[j].first]==n-1)continue;
				if(xj(i,j))b[i].push_back(j),b[j].push_back(i);
			}
		}
		bool fail=0;
		for(int i=1;i<=m;i++)c[i]=0;
		for(int i=1;i<=m;i++)
			if(!c[i]){
				c[i]=1;
				if(!color(i)){fail=1;break;}
			}
		if(fail)printf("NO\n");
		else printf("YES\n");
	}
	return 0;
}

// <planar.cpp> - 02/27/16 04:07:33

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int getint(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

pair <int,int> e[10001];

int hmd[201],c[600];

vector <int> b[600];

bool xj(int x,int y){

int a1=hmd[e[x].first],b1=hmd[e[x].second],a2=hmd[e[y].first],b2=hmd[e[y].second];

if(a1==a2||a1==b2||a2==b1||b1==b2)return 0;

return (a1>a2&&a1<b2)^(b1>a2&&b1<b2);

}

bool color(int x){

for(int i=0;i<b[x].size();i++){

int next=b[x][i];

if(!c[next]){

c[next]=-c[x];

if(!color(next))return 0;

}else if(c[next]==c[x])return 0;

}

return 1;

}

int main(){

int T=getint();

while(T--){

int n=getint(),m=getint();

for(int i=1;i<=m;i++)e[i]=make_pair(getint(),getint());

for(int i=1;i<=n;i++)hmd[getint()]=i;

if(m>3*n-6){printf("NO\n");continue;}

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

if(hmd[e[i].first]>hmd[e[i].second])swap(e[i].first,e[i].second);

for(int i=1;i<=m;i++)b[i].clear();

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

if(hmd[e[i].second]-hmd[e[i].first]==1||hmd[e[i].second]-hmd[e[i].first]==n-1)continue;

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

if(hmd[e[j].second]-hmd[e[j].first]==1||hmd[e[j].second]-hmd[e[j].first]==n-1)continue;

if(xj(i,j))b[i].push_back(j),b[j].push_back(i);

}

bool fail=0;

for(int i=1;i<=m;i++)c[i]=0;

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

if(!c[i]){

c[i]=1;

if(!color(i)){fail=1;break;}

}

if(fail)printf("NO\n");

else printf("YES\n");

}

return 0;

}