题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1997
数据生成器:http://paste.ubuntu.com/22273507/
这个题目在知道了是2-sat的情况下还是懵逼了好久QAQ
当时就想到这个图:一个正方形加上对角线.jpg(solidwork还没装,不想用word画图QAQ
发现他给的这个圆不能自交,于是每一条线就只有两种可能:
1.圆内
2.圆外
于是处理出相互干涉的线段,然后搞2-sat
最开始这么搞了,血RE
遂看题解,™有一个这个结论:
Theorem 1. If v ≥ 3 then e ≤ 3v − 6;
Theorem 2. If v ≥ 3 and there are no cycles of length 3, then e ≤ 2v − 4.
详细情况:https://en.wikipedia.org/wiki/Planar_graph
于是加特判,遂过
#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<set> #include<map> using namespace std; const int MAXN = 20000+9; const int N = 200000; int n,m,que[MAXN],L[MAXN],R[MAXN],T,nxt[N],to[N],head[MAXN],mark[MAXN],cnt; vector<int> G[MAXN]; map<int,int> ins; struct CMP{inline bool operator () (const int &A, const int &B) {return R[A] < R[B];}}; multiset<int,CMP>::iterator itr; multiset<int,CMP> buf; inline int read(){ char c=getchar(); int ret=0; while (c<'0'||c>'9'){c=getchar();} while (c<='9'&&c>='0'){ret=ret*10+c-'0';c=getchar();} return ret; } inline void init(){ n = read(); m = read(); T = 0; for (int i=1;i<=n;i++) G[i].clear(); memset(head,0,sizeof(head)); memset(mark,0,sizeof(mark)); } #define Add_Edge(a,b) to[++T] = b,nxt[T]=head[a],head[a]=T inline void AddEdge(int a, int b) { int ra=a*2+1, rb=b*2+1; a *= 2; b *= 2; Add_Edge(ra,b); Add_Edge(rb,a); Add_Edge(a,rb); Add_Edge(b,ra); } inline void build_map(){ buf.clear(); for (int i=1;i<=n;i++) { while (buf.size() && R[*(buf.begin())] <= i) buf.erase(buf.begin()); for (int j=0,sz=G[i].size();j<sz;j++) for (itr=buf.begin();itr!=buf.end() && R[*itr] < R[G[i][j]];itr++) AddEdge(G[i][j],*itr); for (int j=0,sz=G[i].size();j<sz;j++) buf.insert(G[i][j]); } } bool DFS(int w) { if (mark[w]) return true; if (mark[w^1]) return false; mark[w] = 1; que[++cnt] = w; for (int i=head[w];i;i=nxt[i]) if (!DFS(to[i])) return false; return true; } inline bool judge(){ for (int i=2;i<=m*2+1;i+=2) if (!mark[i] && !mark[i+1]) { cnt = 0; if (DFS(i)) continue; for (int j=1;j<=cnt;j++) mark[que[j]] = 0; cnt = 0; if (!DFS(i+1)) return false; } return true; } int main(){ int TT = read(); while (TT--) { init(); for (int i=1;i<=m;i++) L[i] = read(), R[i] = read(); for (int i=1;i<=n;i++) que[i] = read(), ins[que[i]] = i; for (int i=1;i<=m;i++) { L[i] = ins[L[i]]; R[i] = ins[R[i]]; if (L[i] > R[i]) swap(L[i], R[i]); G[L[i]].push_back(i); } if (m > 3*n-6) printf("NO\n"); else { build_map(); if (judge()) printf("YES\n"); else printf("NO\n"); } } return 0; }