BOJ)2637 장난감조립

문제:icpc.me/2637

장난감 완제품 N을 만드는데 필요한 기본 부품의 종류와 수를 출력하는 문제이다.

여기 기본 부품은 indegree의 수가 0인 정점들이 되고 위상정렬 순서대로 부품의 개수를 중첩 시켜 나가면 답을 구할 수 있다.

a[x][y]가 의미하는건 x번 부품(제품)을 만드는데 필요한 기본 부품 y의 개수이다.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int n, m, a[101][101], in[101], x, y, z;
vector<vector<pair<int, int>>> vt;
int main() {
    scanf("%d%d", &n, &m);
    vt.resize(n + 1);
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d", &x, &y, &z);
        vt[y].emplace_back(x, z);
        in[x]++;
    }
    queue<int> qu;
    for (int i = 1; i <= n; i++) {
        if (!in[i]) {
            qu.push(i);
            a[i][i] = 1;
        }
    }
    while (qu.size()) {
        int here = qu.front();
        qu.pop();
        for (auto there : vt[here]) {
            for (int i = 1; i <= n; i++) 
                a[there.first][i] += there.second*a[here][i];
            in[there.first]--;
            if (!in[there.first])
                qu.push(there.first);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (a[n][i])
            printf("%d %d\n", i, a[n][i]);
    }
    return 0;
}