Poj 1182: 食物鏈

題目

分析

並查集經典題。並查集要記得 init 啊

對於某個動物 x，同時紀錄 x 是物種 A、是物種 B、是物種 C 三種資訊。

編號 x : 代表 x 是物種 A 的資訊 (x:A)
編號 x + N : 代表 x 是物種 B 的資訊 (x:B)
編號 x + 2N : 代表 x 是物種 C 的資訊 (x:C)

在並查集裡同一個 group 代表這些敘述同時成立。

如果 x, y 是同物種，則

unite(x:A, y:A);
unite(x:B, y:B);
unite(x:C, y:C);

錯誤的敘述發生在

已知 x:A 與 y:B 成立 or
已知 x:A 與 y:C 成立 or
已知 x:B 與 y:C 成立 or
已知 x:B 與 y:A 成立 or
已知 x:C 與 y:A 成立 or
已知 x:C 與 y:B 成立

因在 unite 同物種時，三個資訊是同步的，所以上述可以簡化成：

if (same(x:A, y:B) || same(x:A, y:C))

如果 x 吃 y，則（A 吃 B、B 吃 C、C 吃 A）

unite(x:A, y:B);
unite(x:B, y:C);
unite(x:C, y:A);

錯誤發生在

已知 x, y 同物種 or
已知 y 吃 x

即

same(x:A, y:A) or
same(x:A, y:C) or
same(x:B, y:B) or
same(x:B, y:A) or
same(x:C, y:C) or
same(x:C, y:B)

同樣的理由，簡化成：

if (same(x:A, y:A) || same(x:A, y:C))

AC Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

const int MAX_N = 50000;

int N, K;

int parent[MAX_N * 3];
int height[MAX_N * 3];

void init() {
    for (int i = 0; i < 3 * N; i++) {
        parent[i] = i;
        height[i] = 0;
    }
}

int find(int a) {
    if (parent[a] == a)
        return a;
    return parent[a] = find(parent[a]);
}

void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b)
        return;
    if (height[a] < height[b])
        parent[a] = b;
    else {
        parent[b] = a;
        if (height[a] == height[b]) height[a]++;
    }
}

bool same(int a, int b) {
    return find(a) == find(b);
}

int main() {
    scanf("%d %d", &N, &K);

    init();

    int cnt = 0;
    for (int i = 0; i < K; i++) {
        int query, x, y;
        scanf("%d %d %d", &query, &x, &y);
        x--; y--;

        if (x < 0 || x >= N || y < 0 || y >= N) {
            cnt++;
            continue;
        }

        if (query == 1) {
            if (same(x, y + N) || same(x, y + 2 * N)) {
                cnt++;
                continue;
            }

            unite(x, y);
            unite(x + N, y + N);
            unite(x + 2 * N, y + 2 * N);
        }
        else {
            if (same(x, y) || same(x, y + 2 * N) ||
                same(x + N, y + N) || same(x + N, y) ||
                same(x + 2 * N, y + 2 * N) || same(x + 2 * N, y + N)) {
                cnt++;
                continue;
            }

            unite(x, y + N);
            unite(x + N, y + 2 * N);
            unite(x + 2 * N, y);
        }
    }

    printf("%d\n", cnt);

    return 0;
}

amoshyc/poj1182.md

Poj 1182: 食物鏈

題目

分析

AC Code