ZeroJudge B298: 老闆阿我要退貨

台灣的東西真的超好吃，但是最近爆發了食安問題，害得臺灣人心惶惶，引發退貨潮。你家裡剛好買了一大堆月餅，你想要拿去退貨，但是又不知道哪些有問題哪些沒問題。這時天上掉下來一張台灣廠商原料供應圖，你只知道其中某幾家是有問題的，當一家廠商有問題，那它的下游廠商也全都有問題。有了這張圖，你就可以決定要把哪些月餅退貨了!

範例測資

範例輸入範例輸出
第一行有 4 個正整 N、M、L、Q (N、L、Q <= 10000，M <= 100000)，N 為廠商數量 (編號為 1～N)。
接下來 M 行每行有兩個數字 a 和 b，表示 a 廠商供應原料給 b 廠商。
再接下來 L 行，每行有一個數字 x，表示 x 廠商是有問題的。
再接下來 Q 行每行有一個數字 y，詢問 y 廠商是否有問題。		對每一筆詢問，若沒問題則輸出「YA~~」，否則輸出「TUIHUOOOOOO」，一筆詢問一行。
5 3 1 2
1 2
1 3
3 4
3
2
4		YA~~
TUIHUOOOOOO

解題思路

紀錄每一個廠商的下游廠商有誰，在收 L 個有問題的時候將收到的廠商還有他的所有下游廠商做紀錄，可以使用 BFS 的方式來將所有下游廠商跑一遍。在進行 Q 次詢問時只需要看詢問的廠商有沒有被紀錄即可。

範例程式碼－ZeroJudge B298: 老闆阿我要退貨

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int problem[10001] = {}, walk[10001] = {};

vector<int> MAP[10001] = {};

void BFS(const vector<int>start) {
    if (start.size() == 0) return;
    vector<int>newStart;
    map<int, int>push;
    for (int i = 0; i<start.size(); i++) {
        const int num = start[i];
        walk[num]++;
        const vector<int> v = MAP[num];
        for (int j = 0; j<v.size(); j++) {
            const int vv = v[j];
            problem[vv]++;
            if (walk[vv] == 0 && push[vv] == 0) {
                push[vv]++;
                newStart.push_back(vv);
            }
        }
    }
    BFS(newStart);
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N, M, L, Q;
    cin >> N >> M >> L >> Q;
    for (int i = 1; i<=N; i++) {
        problem[i] = 0;
        vector<int> tmp;
        MAP[i] = tmp;
        walk[i] = 0;
    }
    for (int i = 0; i<M; i++) {
        int a, b;
        cin >> a >> b;
        MAP[a].push_back(b);
    }
    for (int i = 0; i<L; i++) {
        int x;
        cin >> x;
        problem[x]++;
        vector<int>tmp;
        tmp.push_back(x);
        BFS(tmp);
    }
    for (int i = 0; i<Q; i++) {
        int y;
        cin >> y;
        if (problem[y] == 0) cout << "YA~~\n";
        else cout << "TUIHUOOOOOO\n";
    }
}

//ZeroJudge B298
//Dr. SeanXD
標籤

相關文章

發佈留言