Chaos Slover 补档计划 - 2-SAT

2015.11.21 18:12 Sat| 4 visits oi_2016| ChaosSlover补档计划| Text

具体细节去看我的 PPT 吧!说起来这些题大概都是按照 hzwer 的刷题记录找来的。

我的博客里面的 POJ 代码还是不能直接通过编译 233

POJ3207 Ikki's Story IV - Panda's Trick

 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
#include <bits/stdc++.h>
using namespace std;

#define t(x) ((x) * 2 - 1)
#define f(x) ((x) * 2)

#define N 2005
#define M 1000005

int n, m, scc, a[N], b[N];
int head[N], deep[N], low[N], inq[N], bel[N];

struct graph
{
    int next, to;
    graph() {}
    graph(int _next, int _to)
    : next(_next), to(_to) {}
} edge[M];

inline void add(int x, int y)
{
    static int cnt = 0;
    edge[++cnt] = graph(head[x], y);
    head[x] = cnt;
}

stack<int> q;

void tarjan(int x)
{
    static int tot = 0;
    low[x] = deep[x] = ++tot;
    q.push(x); inq[x] = true;
    for (int i = head[x]; i; i = edge[i].next)
        if (!deep[edge[i].to])
            tarjan(edge[i].to), low[x] = min(low[x], low[edge[i].to]);
        else if (inq[edge[i].to])
            low[x] = min(low[x], deep[edge[i].to]);
    if (deep[x] == low[x])
    {
        ++scc;
        while (true)
        {
            int now = q.top(); q.pop();
            inq[now] = false; bel[now] = scc;
            if (now == x) break;
        }
    }
}

bool check()
{
    for (int i = 1; i <= m; ++i)
        if (bel[t(i)] == bel[f(i)])
            return false;
    return true;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        cin >> a[i] >> b[i];
        if (a[i] > b[i]) swap(a[i], b[i]);
    }
    for (int i = 1; i <= m; ++i)
        for (int j = i + 1; j <= m; ++j)
            if ((a[j] > a[i] && b[i] > a[j] && b[j] > b[i])
             || (a[i] > a[j] && b[j] > a[i] && b[i] > b[j]))
                add(t(i), f(j)), add(t(j), f(i)),
                add(f(j), t(i)), add(f(i), t(j));
    for (int i = 1; i <= 2 * m; ++i)
        if (!deep[i]) tarjan(i);
    if (check()) puts("panda is telling the truth...");
    else puts("the evil panda is lying again");
    return 0;
}

BZOJ1823 [JSOI2010]满汉全席

 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
#include <bits/stdc++.h>
using namespace std;

#define N 205
#define M 2005

int t, n, m, head[N], cnt;
int tot, scc, deep[N], low[N], inq[N], bel[N];

struct graph
{
    int next, to;
    graph() {}
    graph(int _next, int _to)
    : next(_next), to(_to) {}
} edge[M];

inline void add(int x, int y)
{
    edge[++cnt] = graph(head[x], y);
    head[x] = cnt;
}

inline int read()
{
    int x = 0, f = 0; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == 'm') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * 2 + f;
}

void init()
{
    memset(head, 0, sizeof head);
    memset(deep, 0, sizeof deep);
    cnt = 0; tot = 0; scc = 0;
}

stack<int> q;

void tarjan(int x)
{
    low[x] = deep[x] = ++tot;
    inq[x] = 1; q.push(x);
    for (int i = head[x]; i; i = edge[i].next)
        if (!deep[edge[i].to])
            tarjan(edge[i].to), low[x] = min(low[x], low[edge[i].to]);
        else if (inq[edge[i].to])
            low[x] = min(low[x], deep[edge[i].to]);
    if (deep[x] == low[x])
    {
        ++scc;
        while (true)
        {
            int now = q.top(); q.pop();
            inq[now] = 0;
            bel[now] = scc;
            if (x == now) break;
        }
    }
}

int main()
{
    cin >> t;
    while (t--)
    {
        init();
        cin >> n >> m;
        for (int x, y, i = 1; i <= m; ++i)
        {
            x = read(), y = read();
            add(x % 2 ? x + 1 : x - 1, y);
            add(y % 2 ? y + 1 : y - 1, x);
        }
        for (int i = 1; i <= n * 2; ++i)
            if (!deep[i]) tarjan(i);
        for (int i = 1; i <= n; ++i)
            if (bel[2 * i] == bel[2 * i - 1])
                { puts("BAD"); goto end; }
        puts("GOOD");
        end: ;
    }
    return 0;
}

BZOJ1997 [Hnoi2010]Planar

  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
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
#include <bits/stdc++.h>
using namespace std;

#define t(x) ((x) * 2 - 1)
#define f(x) ((x) * 2)

#define N 20005

int t, n, m, cnt, tot, scc, a[N], b[N];
int head[N], deep[N], low[N], inq[N], bel[N];
map<int, int> mp;

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

struct graph
{
    int next, to;
    graph() {}
    graph(int _next, int _to)
    : next(_next), to(_to) {}
} edge[1000000];

inline void add(int x, int y)
{
    edge[++cnt] = graph(head[x], y);
    head[x] = cnt;
}

void init()
{
    memset(head, 0, sizeof head);
    memset(deep, 0, sizeof deep);
    cnt = tot = scc = 0;
}

stack<int> q;

void tarjan(int x)
{
    low[x] = deep[x] = ++tot;
    q.push(x); inq[x] = true;
    for (int i = head[x]; i; i = edge[i].next)
        if (!deep[edge[i].to])
            tarjan(edge[i].to), low[x] = min(low[x], low[edge[i].to]);
        else if (inq[edge[i].to])
            low[x] = min(low[x], deep[edge[i].to]);
    if (deep[x] == low[x])
    {
        ++scc;
        while (true)
        {
            int now = q.top(); q.pop();
            inq[now] = false; bel[now] = scc;
            if (now == x) break;
        }
    }
}

bool check()
{
    for (int i = 1; i <= m; ++i)
        if (bel[t(i)] == bel[f(i)])
            return false;
    return true;
}

int main()
{
    cin >> t;
    while (t--)
    {
        init();
        cin >> n >> m;
        for (int i = 1; i <= m; ++i)
            a[i] = read(), b[i] = read();
        for (int i = 1; i <= n; ++i)
            mp[read()] = i;
        if (m > 3 * n) { puts("NO"); continue; }
        for (int i = 1; i <= m; ++i)
        {
            a[i] = mp[a[i]]; b[i] = mp[b[i]];
            if (a[i] > b[i]) swap(a[i], b[i]);
        }
        for (int i = 1; i <= m; ++i)
            for (int j = i + 1; j <= m; ++j)
                if ((a[j] > a[i] && b[i] > a[j] && b[j] > b[i])
                 || (a[i] > a[j] && b[j] > a[i] && b[i] > b[j]))
                    add(t(i), f(j)), add(t(j), f(i)),
                    add(f(j), t(i)), add(f(i), t(j));
        for (int i = 1; i <= 2 * m; ++i)
            if (!deep[i]) tarjan(i);
        if (check()) puts("YES");
        else puts("NO");
    }
    return 0;
}

POJ2749 Building roads

  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
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <bits/stdc++.h>
using namespace std;

#define N 1000
#define M 1000000
#define t(x) ((x) * 2 - 1)
#define f(x) ((x) * 2)

struct point
{
    int x, y;
    inline friend istream &operator >>(istream &in, point &p)
    {
        in >> p.x >> p.y;
        return in;
    }
    friend int dist(point p, point q)
    {
        return abs(p.x - q.x) + abs(p.y - q.y);
    }
} s1, s2, p[N];

int n, a, b, tot, ssc, cnt, head[N];
int ax[N], ay[N], bx[N], by[N];
int inq[N], low[N], deep[N], bel[N];
stack<int> q;

struct graph
{
    int next, to;
    graph() {}
    graph(int _next, int _to)
    : next(_next), to(_to) {}
} edge[M];

inline void add(int x, int y)
{
    edge[++cnt] = graph(head[x], y);
    head[x] = cnt;
}

void init()
{
    tot = ssc = cnt = 0;
    memset(head, 0, sizeof head);
    memset(deep, 0, sizeof deep);
}

void tarjan(int x)
{
    low[x] = deep[x] = ++tot;
    inq[x] = 1; q.push(x);
    for (int i = head[x]; i; i = edge[i].next)
        if (!deep[edge[i].to])
            tarjan(edge[i].to), low[x] = min(low[x], low[edge[i].to]);
        else if (inq[edge[i].to])
            low[x] = min(low[x], deep[edge[i].to]);
    if (low[x] == deep[x])
    {
        ++ssc;
        while (true)
        {
            int now = q.top(); q.pop();
            inq[now] = 0;
            bel[now] = ssc;
            if (now == x) break;
        }
    }
}

bool check(int mid)
{
    init();
    for (int i = 1; i <= a; ++i)
    {
        add(t(ax[i]), f(ay[i])), add(t(ay[i]), f(ax[i]));
        add(f(ax[i]), t(ay[i])), add(f(ay[i]), t(ax[i]));
    }
    for (int i = 1; i <= b; ++i)
    {
        add(t(bx[i]), t(by[i])), add(f(bx[i]), f(by[i]));
        add(t(by[i]), t(bx[i])), add(f(by[i]), f(bx[i]));
    }
    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j)
        {
            if (dist(p[i], s1) + dist(p[j], s1) > mid)
                add(t(i), f(j)), add(t(j), f(i));
            if (dist(p[i], s2) + dist(p[j], s2) > mid)
                add(f(i), t(j)), add(f(j), t(i));
            if (dist(p[i], s1) + dist(p[j], s2) + dist(s1, s2) > mid)
                add(t(i), t(j)), add(f(j), f(i));
            if (dist(p[i], s2) + dist(p[j], s1) + dist(s1, s2) > mid)
                add(f(i), f(j)), add(t(j), t(i));
        }
    for (int i = 1; i <= n * 2; ++i)
        if (!deep[i]) tarjan(i);
    for (int i = 1; i <= n; ++i)
        if (bel[t(i)] == bel[f(i)])
            return false;
    return true;
}

int main()
{
    cin >> n >> a >> b;
    cin >> s1 >> s2;
    for (int i = 1; i <= n; ++i)
        cin >> p[i];
    for (int i = 1; i <= a; ++i)
        cin >> ax[i] >> ay[i];
    for (int i = 1; i <= b; ++i)
        cin >> bx[i] >> by[i];
    int l = dist(s1, s2), r = 10000000, ans = -1;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid - 1, ans = mid;
        else l = mid + 1;
    }
    cout << ans << endl;
    return 0;
}

BZOJ2199 [Usaco2011 Jan]奶牛议会

 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
#include <bits/stdc++.h>
using namespace std;

#define N 2005
#define M 8005
#define t(x) ((x) * 2 - 1)
#define f(x) ((x) * 2)

int n, m, head[N], col[N];
char ans[N];
queue<int> q;

struct graph
{
    int next, to;
    graph() {}
    graph(int _next, int _to)
    : next(_next), to(_to) {}
} edge[M];

inline void add(int x, int y)
{
    static int cnt = 0;
    edge[++cnt] = graph(head[x], y);
    head[x] = cnt;
}

bool check(int s)
{
    q.push(s);
    while (!q.empty())
    {
        int x = q.front(); q.pop();
        for (int i = head[x]; i; i = edge[i].next)
            if (col[edge[i].to] != s)
                col[edge[i].to] = s, q.push(edge[i].to);
    }
    for (int i = 1; i <= n; ++i)
        if (col[t(i)] == s && col[f(i)] == s) return false;
    return true;
}

int main()
{
    cin >> n >> m;
    char tx, ty;
    for (int x, y, i = 1; i <= m; ++i)
    {
        scanf("%d %c %d %c\n", &x, &tx, &y, &ty);
        if (tx == 'Y' && ty == 'Y')
            add(f(x), t(y)), add(f(y), t(x));
        else if (tx == 'Y' && ty == 'N')
            add(f(x), f(y)), add(t(y), t(x));
        else if (tx == 'N' && ty == 'Y')
            add(t(x), t(y)), add(f(y), f(x));
        else if (tx == 'N' && ty == 'N')
            add(t(x), f(y)), add(t(y), f(x));
    }
    for (int i = 1; i <= n; ++i)
    {
        bool cx = check(t(i)), cy = check(f(i));
        if (cx && cy) ans[i] = '?';
        else if (cx) ans[i] = 'Y';
        else if (cy) ans[i] = 'N';
        else { puts("IMPOSSIBLE"); return 0; }
    }
    puts(ans + 1);
    return 0;
}

poj3683 Priest John’s Busiest Day

  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
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <bits/stdc++.h>
using namespace std;

#define t(x) ((x) * 2 - 1)
#define f(x) ((x) * 2)

#define N 2005
#define M 8000005

int n, m, scc, a[N], b[N], t[N], d[N], col[N];
int head[N], deep[N], low[N], inq[N], bel[N], con[N];
vector<int> v[N];

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

struct graph
{
    int next, to;
    graph() {}
    graph(int _next, int _to)
    : next(_next), to(_to) {}
} edge[M];

inline void add(int x, int y)
{
    static int cnt = 0;
    edge[++cnt] = graph(head[x], y);
    head[x] = cnt;
}

bool conflict(int s1, int t1, int s2, int t2)
{
    if (max(s1 + t1, s2 + t2) - min(s1, s2) < t1 + t2)
        return true;
    return false;
}

void connect(int x, int y)
{
    if (conflict(a[x], t[x], a[y], t[y]))
        add(t(x), f(y)), add(t(y), f(x));
    if (conflict(a[x], t[x], b[y], t[y]))
        add(t(x), t(y)), add(f(y), f(x));
    if (conflict(b[x], t[x], a[y], t[y]))
        add(f(x), f(y)), add(t(y), t(x));
    if (conflict(b[x], t[x], b[y], t[y]))
        add(f(x), t(y)), add(f(y), t(x));
}

stack<int> q;

void tarjan(int x)
{
    static int tot = 0;
    low[x] = deep[x] = ++tot;
    q.push(x); inq[x] = true;
    for (int i = head[x]; i; i = edge[i].next)
        if (!deep[edge[i].to])
            tarjan(edge[i].to), low[x] = min(low[x], low[edge[i].to]);
        else if (inq[edge[i].to])
            low[x] = min(low[x], deep[edge[i].to]);
    if (deep[x] == low[x])
    {
        ++scc;
        while (true)
        {
            int now = q.top(); q.pop();
            inq[now] = false; bel[now] = scc;
            if (now == x) break;
        }
    }
}

bool check()
{
    for (int i = 1; i <= n; ++i)
        if (bel[t(i)] == bel[f(i)])
            return false;
    return true;
}

void dfs(int x)
{
    if (col[x]) return;
    col[x] = 2;
    for (int i = 0; i < (int)v[x].size(); ++i)
        dfs(v[x][i]);
}

stack<int> s;

void topsort()
{
    for (int i = 1; i <= scc; ++i)
        if (!d[i]) s.push(i);
    while (!s.empty())
    {
        int now = s.top(); s.pop();
        if (col[now]) continue;
        col[now] = 1;
        dfs(con[now]);
        for (int i = 0; i < (int)v[now].size(); ++i)
            if (!(--d[v[now][i]])) s.push(v[now][i]);
    }
}

void print(int x)
{
    static int tot = 0;
    printf("%.2d:%.2d%c", x / 60, x % 60, " \n"[(tot++) & 1]);
}

int main()
{
    n = read();
    for (int i = 1; i <= n; ++i)
    {
        a[i] = read() * 60 + read();
        b[i] = read() * 60 + read() - (t[i] = read());
    }
    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j)
            connect(i, j);
    for (int i = 1; i <= 2 * n; ++i)
        if (!deep[i]) tarjan(i);
    if (!check()) { puts("NO"); return 0; }
    else puts("YES");
    for (int i = 1; i <= 2 * n; ++i)
        for (int j = head[i]; j; j = edge[j].next)
            if (bel[i] != bel[edge[j].to])
                v[bel[edge[j].to]].push_back(bel[i]), ++d[bel[i]];
    for (int i = 1; i <= n; ++i)
        con[bel[t(i)]] = bel[f(i)],
        con[bel[f(i)]] = bel[t(i)];
    topsort();
    for (int i = 1; i <= n; ++i)
    {
        if (col[bel[t(i)]] == 1)
            print(a[i]), print(a[i] + t[i]);
        else
            print(b[i]), print(b[i] + t[i]);
    }
    return 0;
}