1. POJ2236 Wireless Network

题目链接

题意：给出 n 个坏计算机的坐标，两台计算机直接通信最大距离 d，两种操作

  1. “O p”$(1\le p\le n)$表示修复计算机 p.
  2. “S p q”$(1\le p,q\le n)$表示

  O 操作，判断与被修理过的所有计算机能否通信，可以合并所在集合；S 操作，判断两台计算机是否在同一集合。

 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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 1005;

struct point {
    int x, y;
    point() {}
    point(int x, int y) : x(x), y(y) {}
}p[N];

int n, d;
int fa[N], repair[N];

int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

void unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return;
    fa[x] = y;
}

int dis(point a, point b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

int main() 
{
    scanf("%d%d", &n, &d);
    for (int i = 1; i <= n; ++i) fa[i] = i;
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", &p[i].x, &p[i].y);
    }
    char op;
    int a, b, cnt = 0;
    getchar();
    while (~scanf("%c", &op)) {
        if (op == 'O') {
            scanf("%d", &a);
            repair[++cnt] = a;
            for (int i = 1; i < cnt; ++i) {
                if (dis(p[repair[i]], p[a]) <= d * d)
                    unite(repair[i], a);
            }
        }
        else {
            scanf("%d%d", &a, &b);
            if (find(a) == find(b)) puts("SUCCESS");
            else puts("FAIL");
        }
        getchar();
    }
    return 0;
}

2. POJ1611 The Suspects

题目连接

题意：n 个学生$0\sim n-1$，m 个小组，0 号学生是 SARS 疑似病例，一个组有一个疑似病例则该组全部为疑似病例，求疑似病例人数。

 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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 3e4 + 5;

int n, m, k;
int fa[N];

int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

void unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return;
    fa[x] = y;
}

int main() 
{
    while (scanf("%d%d", &n, &m), n || m) {
        for (int i = 0; i < n; ++i) fa[i] = i;
        int x, y;
        while (m--) {
            scanf("%d", &k);
            scanf("%d", &x);
            for (int i = 2; i <= k; ++i) {
                scanf("%d", &y);
                unite(x, y);
            }
        }
        int ans = 1;
        int f0 = find(0);
        for (int i = 1; i < n; ++i)
            if (f0 == find(i)) ans++;
        printf("%d\n", ans);
    }
    return 0;
}

3. HDU1213 How Many Tables

题目链接

题意：n 个人，m 组关系，关系可以传递，求共有多少组关系。

 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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 1005;

int t, n, m;
int fa[N], vis[N];

int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

void unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return;
    fa[x] = y;
}

int main() 
{
    scanf("%d", &t);
    while (t--) {
        memset(vis, 0, sizeof(vis));
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; ++i) fa[i] = i;
        int x, y;
        while (m--) {
            scanf("%d%d", &x, &y);
            unite(x, y);
        }
        int ans = 0;
        for (int i = 1; i <= n; ++i) vis[find(i)] = 1;
        for (int i = 1; i <= n; ++i)
            if (vis[i]) ans++;
        printf("%d\n", ans);
    }
    return 0;
}

4. HDU3038 How Many Answers Are Wrong

题目链接

题意：在区间$[1,n]$上，给定 m 个区间和，问有几个结论矛盾。

 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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 2e5 + 5;

int n, m, ans;
int fa[N], d[N];

int find(int x) {
    if (fa[x] == x) return x;
    int root = find(fa[x]);
    d[x] += d[fa[x]];
    return fa[x] = root;
}

bool Union(int x, int y, int z) {
    int fx = find(x);
    int fy = find(y);
    if (fx == fy) {
        if (d[x] - d[y] == z) return 1;
        return 0;
    }
    fa[fx] = fy;
    d[fx] = d[y] - d[x] + z;
    return 1;
}

int main() 
{
    while (~scanf("%d%d", &n, &m)) {
        memset(d, 0, sizeof(d));
        for (int i = 0; i <= n; ++i) fa[i] = i;
        ans = 0;
        int x, y, z;
        while (m--) {
            scanf("%d%d%d", &x, &y, &z);
            if (!Union(x - 1, y, z)) ans++;
        }
        printf("%d\n", ans);
    }
    return 0;
}

5. POJ1182 食物链

题目链接

题意：$n(1\le n\le50000)$只动物，编号为$1,2,\cdots,n$，属于 A，B，C 的一种。已知 A 吃 B，B 吃 C，C 吃 A。给出以下两种信息$k(1\le k\le100000)$条。

  1. x 和 y 属于同一种
  2. x 吃 y

有一些是相互矛盾的，求不正确信息的条数。

  经典老题，首先我们考虑带权并查集，两个结点有关系，即在同一棵树上find(x) == find(y)，利用 %3 来判断捕食关系。

 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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 5e4 + 5;

int n, k;
int fa[N], r[N];

int find(int x) {
    if (fa[x] == x) return x;
    int root = find(fa[x]);
    r[x] = (r[x] + r[fa[x]]) % 3;
    return fa[x] = root;
}

bool Union(int type, int x, int y) {
    int fx = find(x);
    int fy = find(y);
    if (fx == fy) {
        if ((r[x] - r[y] + 3) % 3 != type) return 1;
        return 0;
    }
    fa[fx] = fy;
    r[fx] = (r[y] - r[x] + type + 3) % 3;
    return 0;
}

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i) fa[i] = i;
    int d, x, y;
    int ans = 0;
    while (k--) {
        scanf("%d%d%d", &d, &x, &y);
        if (x > n || y > n || (x == y && d == 2)) ans++;
        else if (Union(d - 1, x, y)) ans++;
    }
    printf("%d\n", ans);
    return 0;
}

  考虑扩展域并查集，$1\sim n$属于 A 类，$n+1\sim 2n$属于 B 类，$2n + 1\sim 3n$属于 C 类。

 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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 5e4 + 5;

int n, k;
int fa[3 * N], r[3 * N];

int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

void Union(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return;
    if (r[x] < r[y]) fa[x] = y;
    else {
        fa[y] = x;
        if (r[x] == r[y]) r[x]++;
    }
}

bool same(int x, int y) {
    return find(x) == find(y);
}

int main() 
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= 3 * n; ++i) fa[i] = i;
    int d, x, y;
    int ans = 0;
    while (k--) {
        scanf("%d%d%d", &d, &x, &y);
        if (x > n || y > n) { ans++; continue; }
        if (d == 1) {
            if (same(x, y + n) || same(x, y + 2 * n)) ans++;
            else {
                Union(x, y);
                Union(x + n, y + n);
                Union(x + 2 * n, y + 2 * n);
            }
        }
        else {
            if (same(x, y) || same(x, y + 2 * n)) ans++;
            else {
                Union(x, y + n);
                Union(x + n, y + 2 * n);
                Union(x + 2 * n, y);
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

6. POJ1417 True Liars

题目链接

题意：p 个好人，q 个坏人，n 次询问，问 x：y 是好人吗，x 是好人会说实话，否则会说谎，问能否确定所有好人。

  这道题还挺难的，并查集 + dp，回答 yes 说明：x, y 都是好人或都是坏人，回答 no 说明：x, y 一个是好人另一个是坏人。

  先考虑带权并查集(16 ms)，d 数组为与父结点的关系，d[x]=0 表示与父结点同类，d[x]=1表示与父结点异类，dp[i][j] 表示前 i 个集合有 j 个好人的方案数，每个集合分成好人坏人两部分，w[i][0] 和 w[i][1] 表示第 i 个集合两个部分个数，dp[cnt][p] == 1 说明唯一解可行。

 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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 605;

int n, p, q, m, cnt;
int fa[N], d[N], pos[N], mp[N], vis[N];
int dp[N][N], w[N][2];

int find(int x) {
    if (fa[x] == x) return x;
    int root = find(fa[x]);
    d[x] ^= d[fa[x]];
    return fa[x] = root; 
}

void unite(int x, int y, int z) {
    int fx = find(x);
    int fy = find(y);
    if (fx == fy) return;
    fa[fx] = fy;
    d[fx] = d[x] ^ d[y] ^ z;
}

int main() 
{
    while (scanf("%d%d%d", &n, &p, &q), n || p || q) {
        m = p + q;
        for (int i = 1; i <= m; ++i) {
            fa[i] = i, d[i] = 0;
            pos[i] = 0;
            mp[i] = 0;
            vis[i] = -1;
        }
        cnt = 1;
        int x, y;
        char s[5];
        while (n--) {
            scanf("%d%d%s", &x, &y, s);
            if (s[0] == 'y') unite(x, y, 0);
            else unite(x, y, 1);
        }
        for (int i = 1; i <= m; ++i) { // 记录集合个数
            x = find(i);
            if (!pos[x]) {
                pos[x] = cnt;
                w[cnt][0] = 0;
                w[cnt][1] = 0;
                mp[cnt] = x;
                cnt++;
            }
            w[pos[x]][d[i]]++;
        }
        cnt--;
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        for (int i = 1; i <= cnt; ++i) {
            for (int j = 0; j <= p; ++j) {
                if (j - w[i][0] >= 0) {
                    dp[i][j] += dp[i-1][j-w[i][0]];
                }
                if (j - w[i][1] >= 0) {
                    dp[i][j] += dp[i-1][j-w[i][1]];
                }
            }
        }
        if (dp[cnt][p] == 1) {
            for (int i = cnt, j = p; i > 0; --i) { // 回溯路径
                if (dp[i][j] == dp[i-1][j-w[i][0]]) {
                    vis[i] = 0;
                    j -= w[i][0];
                }
                else if (dp[i][j] == dp[i-1][j-w[i][1]]) {
                    vis[i] = 1;
                    j -= w[i][1];
                }
            }
            for (int i = 1; i <= m; ++i) {
                if (vis[pos[fa[i]]] == d[i])
                    printf("%d\n", i);
            }
            puts("end");
        }
        else {
            puts("no");
        }
    }
    return 0;
}

  再考虑扩展域并查集(79 ms)，yes：unite(x, y) and unite(x + m, y + m)，no：unite(x, y + n) and unite(x + n, y)。这样操作下很多集合重复，需要去重。之后 dp 即可。POJ 的 G++ 不支持 auto。

  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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 1205;

int n, p, q, m;
int fa[N], vis[N], dp[N][N], ans[N];
vector<int> v[N];
vector<int> w1[N];
vector<int> w2[N];

int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

void unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return;
    fa[x] = y;
}

int main() 
{
    while (scanf("%d%d%d", &n, &p, &q), n || p || q) {
        m = p + q;
        for (int i = 1; i <= 2 * m; ++i) {
            fa[i] = i;
            ans[i] = 0;
            v[i].clear();
            w1[i].clear(); w2[i].clear();
            vis[i] = 0;
        }
        int x, y;
        char s[5];
        while (n--) {
            scanf("%d%d%s", &x, &y, s);
            if (s[0] == 'y') {
                unite(x, y);
                unite(x + m, y + m);
            }
            else {
                unite(x, y + m);
                unite(x + m, y);
            }
            
        }
        for (int i = 1; i <= 2 * m; ++i) {
            int x = find(i);
            v[x].push_back(i);
        }
        int cnt = 1;
        for (int i = 1; i <= 2 * m; ++i) {
            int flag = 0;
            int size = v[i].size();
            for (int j = 0; j < size; ++j) {
                if (v[i][j] <= m) {
                    if (vis[v[i][j]]) continue;
                    vis[v[i][j]] = 1;
                    flag = 1;
                    w1[cnt].push_back(v[i][j]);
                }
                else {
                    if (vis[v[i][j] - m]) continue;
                    vis[v[i][j] - m] = 1;
                    flag = 1;
                    w2[cnt].push_back(v[i][j] - m);
                }
            }
            if (flag) cnt++;
        }
        cnt--;
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        for (int i = 1; i <= cnt; ++i) {
            int s1 = w1[i].size(), s2 = w2[i].size();
            for (int j = p; j >= s1; --j) {
                dp[i][j] += dp[i-1][j-s1];
            }
            for (int j = p; j >= s2; --j) {
                dp[i][j] += dp[i-1][j-s2];
            }
        }
        if (dp[cnt][p] == 1) {
            for (int i = cnt, j = p; i > 0; --i) {
                int s1 = w1[i].size(), s2 = w2[i].size();
                if (dp[i][j] == dp[i-1][j-s1]) {
                    for (int k = 0; k < s1; ++k) ans[w1[i][k]] = 1;
                    j -= s1;
                }
                else if (dp[i][j] == dp[i-1][j-s2]) {
                    for (int k = 0; k < s2; ++k) ans[w2[i][k]] = 1;
                    j -= s2;
                }
            }
            for (int i = 1; i <= m; ++i) {
                if (!ans[i]) continue;
                printf("%d\n", i);
            }
            puts("end");
        }
        else puts("no");
    }
    return 0;
}

7. POJ1456 Supermarket

题目链接

题意：给定 n 个商品，每个商品有利润 $p_i$ 和过期时间 $d_i$，每天只能卖出一个商品，过期商品不能再卖，问如何安排销售日期，使利润最大。

  主要是贪心思想，当前最贵的商品最大限度地晚卖。

 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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 1e4 + 5;

struct node {
    int pri, day;
    friend bool operator < (const node &a, const node &b) {
        return a.pri > b.pri;
    }
}p[N];

int n;
int pre[N];

int find(int x) {
    if (pre[x] == -1) return x;
    return pre[x] = find(pre[x]);
}

int main() 
{
    while (~scanf("%d", &n)) {
        memset(pre, -1, sizeof(pre));
        for (int i = 1; i <= n; ++i)
            scanf("%d%d", &p[i].pri, &p[i].day);
        sort(p + 1, p + n + 1);
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            int time = find(p[i].day);
            if (time > 0) {
                ans += p[i].pri;
                pre[time] = time - 1;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

8. POJ1733 Parity game

题目链接

题意：给出一个长度为 $n(n\le10^9)$ 的由 0 和 1 组成的序列 $S$，$m$ 个回答 $S[l\sim r]$中有奇数个 1 还是偶数个 1，输出从哪一条开始下一条错了，如果均正确输出 $m$。

  n 很大，离散化处理，d[x] 为 0 表示 x 与 fa[x] 奇偶性相同，为 1 表示 x 与 fa[x] 奇偶性不同。x 和 y 不在同一集合进行合并，d[fx] = d[x] xor d[y] xor ans[i]，否则进行判断。

 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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 2e4 + 5, M = 1e4 + 5;

int n, m, cnt;
int a[N], fa[N], d[N];
int l[M], r[M], ans[M];

int find(int x) {
    if (fa[x] == x) return x;
    int root = find(fa[x]);
    d[x] ^= d[fa[x]];
    return fa[x] = root;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        char str[5];
        scanf("%d%d%s", &l[i], &r[i], str);
        ans[i] = (str[0] == 'o' ? 1 : 0);
        a[++cnt] = l[i] - 1;
        a[++cnt] = r[i];
    }
    sort(a + 1, a + cnt + 1);
    n = unique(a + 1, a + cnt + 1) - a - 1;
    for (int i = 1; i <= n; ++i) fa[i] = i;
    for (int i = 1; i <= m; ++i) {
        int x = lower_bound(a + 1, a + n + 1, l[i] - 1) - a;
        int y = lower_bound(a + 1, a + n + 1, r[i]) - a;
        int fx = find(x), fy = find(y);
        if (fx == fy) {
            if ((d[x] ^ d[y]) != ans[i]) {
                printf("%d\n", i - 1);
                return 0;
            }
        }
        else {
            fa[fx] = fy;
            d[fx] = d[x] ^ d[y] ^ ans[i];
        }
    }
    printf("%d\n", m);
    return 0;
}

9. POJ1984 Navigation Nightmare

题目链接

题意：n 个农场，m 条信息：F1 F2 L D 表示 F2 再农场 F1 的 D 方向的 L 距离处，k 个问题：F1 F2 I 表示知道第一到第 I 条信息情况下，求 F1 和 F2 的曼哈顿距离，无法求出输出 -1。

  rx[] 记录与父结点的水平距离，ry[] 记录与父结点的垂直距离。以向东为正方向，更新时 rx[fx] = -rx[x] + ry[y] + dx[cnt]，ry[fx] = -ry[x] + ry[y] + dy[cnt]。询问时，同根输出 abs(rx[x] - rx[y]) + abs(ry[x] - ry[y])，不同根无法判断关系输出 -1。

 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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 4e4 + 5, K = 1e4 + 5;

struct query {
    int x, y, index, id;
    friend bool operator < (const query &a, const query &b) {
        return a.index < b.index;
    }
}q[K];

int n, m, l, k;
char dir;
int fa[N], rx[N], ry[N];
int u[N], v[N], dx[N], dy[N];
int ans[K];

int find(int x) {
    if (fa[x] == x) return x;
    int root = find(fa[x]);
    rx[x] += rx[fa[x]];
    ry[x] += ry[fa[x]];
    return fa[x] = root;
}

int main() 
{
    while (~scanf("%d%d", &n, &m)) {
        for (int i = 1; i <= n; ++i) {
            fa[i] = i;
            rx[i] = ry[i] = 0;
        }
        for (int i = 1; i <= m; ++i) {
            scanf("%d%d%d %c", &u[i], &v[i], &l, &dir);
            if (dir == 'N') { dx[i] = 0; dy[i] = l; }
            else if (dir == 'E') { dx[i] = l; dy[i] = 0; }
            else if (dir == 'S') { dx[i] = 0; dy[i] = -l; }
            else if (dir == 'W') { dx[i] = -l; dy[i] = 0; }
        }
        scanf("%d", &k);
        for (int i = 1; i <= k; ++i) {
            scanf("%d%d%d", &q[i].x, &q[i].y, &q[i].index);
            q[i].id = i;
        }
        sort(q + 1, q + k + 1);
        int cnt = 1;
        for (int i = 1; i <= k; ++i) {
            while (cnt <= q[i].index) {
                int fx = find(u[cnt]);
                int fy = find(v[cnt]);
                fa[fx] = fy;
                rx[fx] = -rx[u[cnt]] + rx[v[cnt]] + dx[cnt];
                ry[fx] = -ry[u[cnt]] + ry[v[cnt]] + dy[cnt];
                cnt++;
            }
            if (find(q[i].x) != find(q[i].y)) ans[q[i].id] = -1;
            else {
                ans[q[i].id] = abs(rx[q[i].x] - rx[q[i].y]) + abs(ry[q[i].x] - ry[q[i].y]);
            }
        }
        for (int i = 1; i <= k; ++i) printf("%d\n", ans[i]);
    }
    return 0;
}

10. POJ2492 A Bug’s Life

题目链接

题意：t 组数据，每组 n 条虫，m 个关系 x y 表示 x 和 y 为异性，判断是否有矛盾。

 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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 2005;

int t, n, m, cnt, flag;
int fa[N], d[N];

int find(int x) {
    if (fa[x] == x) return x;
    int root = find(fa[x]);
    d[x] ^= d[fa[x]];
    return fa[x] = root;
}

bool Union(int x, int y) {
    int fx = find(x);
    int fy = find(y);
    if (fx == fy) {
        if ((d[x] ^ d[y]) == 1) return 1;
        return 0;
    }
    fa[fx] = fy;
    d[fx] = d[x] ^ d[y] ^ 1;
    return 1;
}

int main() 
{
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; ++i) fa[i] = i;
        memset(d, 0, sizeof(d));
        int x, y;
        flag = 0;
        while (m--) {
            scanf("%d%d", &x, &y);
            if (!Union(x, y)) flag = 1;
        }
        printf("Scenario #%d:\n", ++cnt);
        if (flag) puts("Suspicious bugs found!\n");
        else puts("No suspicious bugs found!\n");
    }
    return 0;
}

11. POJ2912 Rochambeau

题目链接

题意：n 个小孩进行猜拳，其中一个是裁判，剩下的小孩分成三组，同一组的小孩出同一种手势，裁判可以任意出，给出 m 次猜拳结果，问最早在第几次猜拳结果后知道裁判是谁。

  枚举第 i 人为裁判，则除第 i 人外其他人判断应该无冲突，d[x] = 0：x 与 fa[x] 同类，d[x] = 1：x 吃 fa[x]：d[x] = 2，x 被 fa[x] 吃，最小的行数需要取最大值，更早的行数不能否定到只剩一人。

 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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 505, M = 2005;

int n, m, k, flag, pos, id, cnt;
int fa[N], d[N];
int u[M], v[M];
char op[M];

int find(int x) {
    if (fa[x] == x) return x;
    int root = find(fa[x]);
    d[x] = (d[x] + d[fa[x]]) % 3;
    return fa[x] = root;
}

bool Union(int x, int y, int z) {
    int fx = find(x);
    int fy = find(y);
    if (fx == fy) {
        return (d[x] - d[y] + 3) % 3 != z;
    }
    fa[fx] = fy;
    d[fx] = ((d[y] - d[x] + z) % 3 + 3) % 3;
    return 0;
}

int main() 
{
    while (~scanf("%d%d", &n, &m)) {
        for (int i = 1; i <= m; ++i) {
            scanf("%d%c%d", &u[i], &op[i], &v[i]);
        }
        pos = id = cnt = 0;
        for (int i = 0; i < n; ++i) {
            flag = 1;
            for (int j = 0; j <= n; ++j) fa[j] = j;
            memset(d, 0, sizeof(d));
            for (int j = 1; j <= m; ++j) {
                if (u[j] == i || v[j] == i) continue;
                if (op[j] == '=') k = 0;
                else if (op[j] == '<') k = 1;
                else if (op[j] == '>') k = 2;
                if (Union(u[j], v[j], k)) {
                    pos = max(pos, j);
                    flag = 0;
                    break;
                }
            }
            if (flag) {
                cnt++;
                id = i;
            }
        }
        if (!cnt) puts("Impossible");
        else if (cnt == 1) printf("Player %d can be determined to be the judge after %d lines\n", id, pos);
        else if (cnt > 1) puts("Can not determine");
    }
    return 0;
}

12. ZOJ3261 Connections in Galaxy War

题目链接

题意：编号从 0 到 n - 1 的 n 个点，每个点有一个非负权值 $p_i$。给出 m 条边和 q 个操作，每个操作有两种形式，destroy a b：摧毁 a, b 之间的边，query a：询问从 a 出发能到达的点，点权比 a 大的最大权值点，权值最大条件下编号最小的点，若没有这样的点输出 -1。

  按照题意在线去边不方便，考虑离线记录操作逆向将破坏的边添加，点权大且标号小的为祖先。

 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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 5e4 + 5;

struct node {
    char s[10];
    int a, b;
}q[N];

int n, m, k, cnt;
int fa[N], p[N], u[N], v[N], ans[N];
map<int, map<int, bool> > mp;

int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

void unite(int x, int y) {
    int fx = find(x);
    int fy = find(y);
    if (fx == fy) return;
    if (p[fx] < p[fy] || (p[fx] == p[fy] && fx > fy)) fa[fx] = fy;
    else fa[fy] = fx;
}

int main() 
{
    int flag = 0;
    while (~scanf("%d", &n)) {
        for (int i = 0; i <= n; ++i) fa[i] = i;
        mp.clear();
        for (int i = 0; i < n; ++i) scanf("%d", &p[i]);
        scanf("%d", &m);
        for (int i = 1; i <= m; ++i) {
            scanf("%d%d", &u[i], &v[i]);
        }
        scanf("%d", &k);
        for (int i = 1; i <= k; ++i) {
            scanf("%s", q[i].s);
            if (q[i].s[0] == 'q') scanf("%d", &q[i].a);
            else {
                scanf("%d%d", &q[i].a, &q[i].b);
                mp[q[i].a][q[i].b] = mp[q[i].b][q[i].a] = 1;
            }
        }
        for (int i = 1; i <= m; ++i) {
            if (!mp[u[i]][v[i]]) unite(u[i], v[i]);
        }
        cnt = 0;
        for (int i = k; i >= 1; --i) {
            if (q[i].s[0] == 'd') {
                unite(q[i].a, q[i].b);
            }
            else {
                int x = q[i].a;
                int fx = find(x);
                ans[++cnt] = p[fx] > p[x] ? fx : -1;
            }
        }
        if (flag) puts("");
        flag = 1;
        for (int i = cnt; i >= 1; --i) {
            printf("%d\n", ans[i]);
        }
    }
    return 0;
}

13. HDU1272 小希的迷宫

题目链接

题意：无向图判环。

 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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 1e5 + 5;

int fa[N], v[N];

int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

int Union(int x, int y) {
    int fx = find(x);
    int fy = find(y);
    if (fx == fy) return 0;
    fa[fx] = fy;
    return 1;
}

int main() 
{
    int x, y;
    while (scanf("%d%d", &x, &y), ~x || ~y) {
        if (!x && !y) { puts("Yes"); continue; }
        for (int i = 1; i <= N; ++i) fa[i] = i;
        memset(v, 0, sizeof(v));
        v[x] = v[y] = 1;
        int flag = Union(x, y);
        while (scanf("%d%d", &x, &y), x && y) {
            if (!flag) continue;
            v[x] = v[y] = 1;
            if (!Union(x, y)) flag = 0;
        }
        if (!flag) { puts("No"); continue; }
        int sum = 0; // 集合个数
        for (int i = 1; i < N; ++i) {
            if (v[i] && fa[i] == i) sum++;
        }
        if (sum > 1) puts("No");
        else puts("Yes");
    }
    return 0;
}

14. POJ1308 Is It A Tree?

题目链接

题意：和上题一模一样。

 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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 1e5 + 5;

int fa[N], v[N];

int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

int Union(int x, int y) {
    int fx = find(x);
    int fy = find(y);
    if (fx == fy) return 0;
    fa[fx] = fy;
    return 1;
}

int main() 
{
    int x, y, cnt = 0;
    while (scanf("%d%d", &x, &y), ~x || ~y) {
        if (!x && !y) { printf("Case %d is a tree.\n", ++cnt); continue; }
        for (int i = 1; i <= N; ++i) fa[i] = i;
        memset(v, 0, sizeof(v));
        v[x] = v[y] = 1;
        int flag = Union(x, y);
        while (scanf("%d%d", &x, &y), x && y) {
            if (!flag) continue;
            v[x] = v[y] = 1;
            if (!Union(x, y)) flag = 0;
        }
        if (!flag) { printf("Case %d is not a tree.\n", ++cnt); continue; }
        int sum = 0;
        for (int i = 1; i < N; ++i) {
            if (v[i] && fa[i] == i) sum++;
        }
        if (sum > 1) printf("Case %d is not a tree.\n", ++cnt);
        else printf("Case %d is a tree.\n", ++cnt);
    }
    return 0;
}