学海泛舟

poj 3207 Ikki's Story IV - Panda's Trick 题解

发表于 | 分类于 |

原题

传送门

题目大意

圆上有n个点，连接其中m对点，可以选择在圆外或圆内连线，问能否使所有的连线都不相交。

分析

注意到连线只有两种状态，在圆外连或者在圆内连，就很容易联想到2-SAT。
将每一条连线都看作两个点，分别代表连线处于圆内和连线处于圆外。
对于有可能相交的连线，就当作一种约束条件。
当然要注意这里是无向边。

参考代码

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<map>
#include<climits>
#include<cmath>
using namespace std;
const int maxn=5500;
struct Edge{
	int to,next;
}edge[500*500+100];
int head[maxn],tot;
void addedge(int u,int v){
	edge[tot].to=v;
	edge[tot].next=head[u];
	head[u]=tot++;
}
int scc,Low[maxn],DFN[maxn],Stack[maxn],top,Index,Belong[maxn];
bool Instack[maxn];
void tarjan(int u){
	int v;
	Low[u]=DFN[u]=++Index;
	Stack[top++]=u;
	Instack[u]=true;
	for(int i=head[u];~i;i=edge[i].next){
		v=edge[i].to;
		if(!DFN[v]){
			tarjan(v);
			if(Low[u]>Low[v]) Low[u]=Low[v];
		} else if(Instack[v]&&Low[u]>DFN[v])
			Low[u]=DFN[v];
	}
	if(Low[u]==DFN[u]){
		scc++;
		do{
			v=Stack[--top];
			Instack[v]=false;
			Belong[v]=scc;
		} while(v!=u);
	}
}
void solve(int N){
	memset(DFN,0,sizeof DFN);
	memset(Instack,false,sizeof Instack);
	Index=scc=top=0;
	for(int i=0;i<N;++i)
		if(!DFN[i])
			tarjan(i);
}
void init(){
	tot=0;
	memset(head,-1,sizeof head);
}
int a[2010],b[2010];
int main(){
	int n,m;
	init();
	scanf("%d %d",&n,&m);
	for(int i=0;i<m;++i){
		scanf("%d %d",a+i,b+i);
		if(a[i]>b[i]) swap(a[i],b[i]);
	}
	for(int i=0;i<m;++i)
		for(int j=i+1;j<m;++j)
			if((a[i]<=a[j]&&b[i]>=a[j]&&b[i]<=b[j])||(a[i]>=a[j]&&a[i]<=b[j]&&b[i]>=b[j])){
				addedge(i<<1,j<<1|1);
				addedge(j<<1,i<<1|1);
				addedge(i<<1|1,j<<1);
				addedge(j<<1|1,i<<1);
			}
	solve(2*m);
	bool flag=true;
	for(int i=0;i<2*m;i+=2){
		if(Belong[i]==Belong[i^1]){
			flag=false;
			break;
		}
	}
	if(flag) printf("panda is telling the truth...\n");
	else printf("the evil panda is lying again\n");
	return 0;
}