티스토리 뷰

알고리즘 관련/BOJ

BOJ)2637 장난감조립

JASON 자손9319 2017. 1. 22. 18:26

문제:icpc.me/2637


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


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


a[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
#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<intint>>> 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;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)4196 도미노  (0) 2017.01.24
BOJ)3665 최종 순위  (2) 2017.01.22
BOJ)2637 장난감조립  (0) 2017.01.22
BOJ)9470 Strahler 순서  (0) 2017.01.22
BOJ)13711 LCS4  (0) 2017.01.22
BOJ)1183 약속  (0) 2017.01.22
댓글
댓글쓰기 폼