【题目链接】
http://poj.org/problem?id=3207
【题目大意】
一个圆圈上有N个数:0,1,2……N-1。 然后有m条线两两连接这些点,这些线可以在圆圈里面,也可以在圆圈外面。问有没有一种方式,使得这些线都不相交。
【思路】
以线为单位,每条线要么在圆圈里面,要么在圆圈外面,典型的2-SAT模型。
【代码】
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long int64;
const int MAXN = 1010;
const int VN = MAXN*2;
const int EN = VN*VN/2;
int n, m;
int arr[VN][2];
struct Graph{
int size;
int head[VN];
struct{
int v, next;
}E[EN];
void init(){
size = 0;
memset(head, -1, sizeof(head));
}
void addEdge(int u, int v){
E[size].v = v;
E[size].next = head[u];
head[u] = size++;
}
}g;
class Two_Sat{
public:
bool check(const Graph& g, const int n){
scc(g, n);
for(int i=0; i<n; ++i)
if(belong[i] == belong[i+n])
return false;
return true;
}
private:
void tarjan(const Graph& g, const int u){
int v;
DFN[u] = low[u] = ++idx;
sta[top++] = u;
instack[u] = true;
for(int e=g.head[u]; e!=-1; e=g.E[e].next){
v = g.E[e].v;
if(DFN[v] == -1){
tarjan(g, v);
low[u] = min(low[u], low[v]);
}else if(instack[v]){
low[u] = min(low[u], DFN[v]);
}
}
if(DFN[u] == low[u]){
++bcnt;
do{
v = sta[--top];
instack[v] = false;
belong[v] = bcnt;
}while(u != v);
}
}
void scc(const Graph& g, const int n){
idx = top = bcnt = 0;
memset(DFN, -1, sizeof(DFN));
memset(instack, 0, sizeof(instack));
for(int i=0; i<2*n; ++i)
if(DFN[i] == -1)
tarjan(g, i);
}
private:
int idx, top, bcnt;
int DFN[VN];
int low[VN];
int sta[VN];
int belong[VN];
bool instack[VN];
}sat;
bool isCross(int* A, int *B){
return A[0]>B[0]&&A[0]<B[1] && (A[1]<B[0] || A[1]>B[1])
|| A[1]>B[0]&&A[1]<B[1] && (A[0]<B[0] || A[0]>B[1]);
}
int main(){
while(~scanf("%d%d", &n, &m)){
g.init();
for(int i=0; i<n; ++i){
scanf("%d%d", &arr[i][0], &arr[i][1]);
if(arr[i][0] > arr[i][1]) swap(arr[i][0], arr[i][1]);
}
for(int i=0; i<n; ++i){
for(int j=i+1; j<n; ++j){
if(isCross(arr[i], arr[j])) {
g.addEdge(i, j+n);
g.addEdge(i+n, j);
g.addEdge(j, i+n);
g.addEdge(j+n, i);
}
}
}
if(sat.check(g, n)) puts("panda is telling the truth...");
else puts("the evil panda is lying again");
}
return 0;
}
分享到:
相关推荐
POJ水题集-----50道左右-----增加自信啊..
用Java代码实现POJ(PKU)上题2494!
很有用的解题报告。。是acm初级提高的必备资料。。。。。
北大POJ2002-Squares 解题报告+AC代码
北大POJ3292-Semi-prime H-numbers 解题报告+AC代码
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码
East Central North America 1999。50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50...
poj 1000 - 2000 部分题目 官方分类 poj 1000 - 2000 部分题目 官方分类
2 ABC 3 BCEF 4 ADG 5 BDEFH 6 CFI 7 DEGH 8 GHI 9 EFHI (图 2) 输入 从标准输入设备读入9个整数,表示各时钟指针的起始位置。1=12点、1=3点、2=6点、3=9点。 输出 输出一个最短的移动序列,使得9个时钟的指针都...
非常全的poj答案库 1164-1874 1000-4007
poj 1690 Your-Term-Project.md
这是我个人写的POJ上2314题的Java实现,希望对喜欢ACM的人有帮助
poj 1240 Pre-Post-erous!.md
西北工业大学-c语言-POJ-题目及答案-第七季.doc
北大POJ2262-Goldbach's Conjecture 解题报告+AC代码
北大POJ1258-Agri-Net【Prim】 解题报告+AC代码
poj 1028 Web Navigation 的代码,已通过!
北大POJ2388-Who's in the Middle 解题报告+AC代码
POJ3211--Washing Clothes
北大POJ2305-Basic remains POJ2305-Basic remains