POJ3207Ikki's Story IV

题意：平面上，一个圆，圆的边上按顺时针放着n个点。现在要连m条边，比如a，b，那么a到b可以从圆的内部连接，也可以从圆的外部连接。给你的信息中，每个点最多只会连接的一条边。问能不能连接这m条边，使这些边都不相交。

分析：将每一条边缩成一个点，对于每条边要么在圆内要么在园外只有满足一种情况，将在圆内设为i，在圆外设为i',那么对于两条线（i, j）不能同时在圆内，那么也不能同时在圆外。则有四种情况（i, j') (i', j) (j, i') (j', i)要建这四条边，然后就照着刘汝佳书上的抄了

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <vector>
 5 #include <cmath>
 6 #include <stack>
 7 #include <algorithm>
 8 using namespace std;
 9 const int Max = 1200;
10 struct TWOSAT
11 {
12     int n;
13     vector<int> G[Max * 2];
14     bool mark[Max * 2];
15     int S[Max * 2], c;
16     void init(int n)
17     {
18         this->n = n;
19         for (int i = 0; i <= n * 2; i++)
20             G[i].clear();
21         memset(mark, 0, sizeof(mark));
22     }
23     void add_clause(int x, int y)
24     {
25         G[2 * x].push_back(2 * y + 1);  //四条边
26         G[2 * x + 1].push_back(2 * y);
27         G[2 * y + 1].push_back(2 * x);
28         G[2 * y].push_back(2 * x + 1);
29     }
30     bool dfs(int x)
31     {
32         if (mark[x ^ 1])
33             return false;
34         if (mark[x])
35             return true;
36         mark[x] = true;
37         S[c++] = x;
38         for (int i = 0; i < (int) G[x].size(); i++)
39             if (!dfs(G[x][i]))
40             return false;
41         return true;
42     }
43     bool solve()
44     {
45         for (int i = 2; i <= n * 2; i += 2)
46         {
47             if (!mark[i] && !mark[i + 1])
48             {
49                 c = 0;
50                 if (!dfs(i))
51                 {
52                     while (c > 0)
53                         mark[ S[--c] ] = false;
54                     if (!dfs(i + 1))
55                         return false;
56                 }
57             }
58         }
59         return true;
60     }
61 };
62 struct Node
63 {
64     int s, t;
65 }node[Max];
66 int main()
67 {
68     int n, m;
69     while (scanf("%d%d", &n, &m) != EOF)
70     {
71         for (int i = 1; i <= m; i++)
72         {
73             scanf("%d%d", &node[i].s, &node[i].t);
74             if (node[i].s > node[i].t)  //这一步让判断相交很方便
75                 swap(node[i].s, node[i].t);
76         }
77         TWOSAT twosat;
78         twosat.init(m);
79         for (int i = 1; i <= m; i++)
80         {
81             for (int j = i + 1; j <= m; j++)
82             {
83                 if ( (node[i].s < node[j].s && node[i].t < node[j].t && node[i].t > node[j].s) || (node[j].s < node[i].s && node[i].t > node[j].t && node[j].t > node[i].s) )  //相交的情况， i 的起点 在 j 的 起点和终点之间并且i的终点要大于j的终点， 另一种情况类似
84                 {
85                     twosat.add_clause(i, j);
86                 }
87             }
88         }
89         if (twosat.solve())
90             printf("panda is telling the truth...
");
91         else
92             printf("the evil panda is lying again
");
93     }
94 }

View Code