题意：
panda和ikki.玩游戏..
给出m个点对关系..这些点都在圆上..
给点对连线..如果可以不交叉(可以在圆内或圆外连线)则panda赢..否则ikki.赢
输入：
给出n m 表示有n个点 m个点对
接下来m行 有a b 表示点a 和 点b 之间有一条线
思路：
2-sat..用来解决2个集合的冲突问题..
这道题..冲突在于是在圆内和在圆外..
把边看成点..
然后看所有边连起来之后会不会出现冲突..即在圆外的边和在圆内的边同时出现在一个强连通分量里了..
所以求出强连通分量..
看交叉的两条边..用tarjan染色..
如果冲突出现了(在圆内和在圆外出现在同一个分量里..则panda输了..)
Tips：
nothing..？
Code：
View Code 1 #include2 #include 3 #include 4 using namespace std; 5 #define clr(x) memset(x, 0, sizeof(x)) 6 const int INF = 0x1f1f1f1f; 7 const int MAXN = 510; 8 9 struct Node 10 { 11 int x; 12 int y; 13 }node[MAXN]; 14 15 struct Edge 16 { 17 int to; 18 int next; 19 }edge[1000010]; 20 int head[MAXN]; 21 int tot; 22 23 void add(int s, int u) 24 { 25 edge[tot].to = u; 26 edge[tot].next = head[s]; 27 head[s] = tot++; 28 29 edge[tot].to = s; 30 edge[tot].next = head[u]; 31 head[u] = tot++; 32 } 33 34 int low[MAXN], dfn[MAXN]; 35 int sta[MAXN], ins[MAXN], col[MAXN]; 36 int ti, top, cnt; 37 void tarjan(int u) 38 { 39 int i, j, k; 40 dfn[u] = low[u] = ++ti; 41 ins[u] = 1; 42 sta[++top] = u; 43 for(i = head[u]; i != -1; i = edge[i].next) { 44 k = edge[i].to; 45 if(!dfn[k]) { 46 tarjan(k); 47 low[u] = min(low[u], low[k]); 48 } else if(ins[k]) { 49 low[u] = min(low[u], dfn[k]); 50 } 51 } 52 if(low[u] == dfn[u]) { 53 cnt++; 54 do 55 { 56 k = sta[top--]; 57 col[k] = cnt; 58 ins[k] = 0; 59 }while(u != k); 60 } 61 } 62 63 64 int n, m; 65 66 void solve_ta() 67 { 68 int i, j, k; 69 clr(dfn); 70 ti = top = cnt = 0; 71 for(i = 1; i <= m; ++i) 72 if(!dfn[i]) 73 tarjan(i); 74 } 75 76 bool solve() 77 { 78 int i, j, k; 79 solve_ta(); 80 for(i = 1; i <= m; ++i) 81 if(col[i] == col[i+m]) return false; 82 return true; 83 } 84 85 int main() 86 { 87 int i, j, k; 88 int a, b; 89 while(scanf("%d %d", &n, &m) != EOF) 90 { 91 tot = 0; 92 memset(head, 0xff, sizeof(head)); 93 94 for(i = 1; i <= m; ++i) { 95 scanf("%d %d", &a, &b); 96 if(a > b) 97 swap(a, b); 98 node[i].x = a, node[i].y = b; 99 }100 101 for(i = 1; i <= m; ++i)102 for(j = i+1; j <= m; ++j)103 if((node[i].x > node[j].x && node[i].x < node[j].y && node[i].y > node[j].y)104 ||(node[j].x > node[i].x && node[j].x < node[i].y && node[j].y > node[j].y)){105 add(i, j+m);106 add(j, i+m);107 }108 109 bool flag = solve();110 if(flag) puts("panda is telling the truth...");111 else puts("the evil panda is lying again");112 }113 return 0;114 }
题目链接：