继续刷。。【写完这个题解还是复习一下的好
首先我们把哈密顿回路展成一个圆。。那么其他的边就是圆上的弧
如果弧相互交叉了我们可以将其中一个翻到外面去。。但是不能同时翻两个
于是在相互交叉的弧之间连边然后黑白染色即可。。
发现边数最大有10000。。
但是伟大的欧拉告诉我们平面图中m<=3n-6
特判掉不符合的，所以边数最多只有594条了。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
// <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; } |
说点什么