【アルゴリズム問題】yukicoder no.30 たこやき工場 (by なおさん)(level ☆☆)
閉じる
閉じる

新しい記事を投稿しました。シェアして読者に伝えましょう

×

【アルゴリズム問題】yukicoder no.30 たこやき工場 (by なおさん)(level ☆☆)

2014-09-25 23:20


    太郎君はとある工場を建てようとしています。
    効率よく生産するためには、材料を計画的に購入しなければなりません。

    この工場では、最終的に製造したい製品を 製品番号N とし、
    製品番号1 ~ N-1 の中間素材となる製品を取り扱います。

    製品番号1 ~ N-1 の製品は、外部から購入するか
    またはこの工場で製造するかのどちらかにより手に入るものとします。
    また、最終製品Nも含め、製造することが出来る製品は、
    外部から購入せずに必ず製造するものとします。

    入力に、各製品番号(1~N)の製造方法
    (材料の製品番号・個数と、その材料から1個製造できる製品番号)
    が与えられるので、
    製品iの製造方法が複数書かれている場合は、それらすべての材料が必要である。

    最終製品Nを1個作るために、外部から購入する必要のある最小の個数を
    1~N-1番の 製品番号ごとにそれぞれ1行で出力してください。
    行の末尾には改行を出力してください。

    製品Nを製造するための製造方法は必ず与えられます。


    【入力】
    N
    M
    P1 Q1 R1
    P2 Q2 R2
    ...
    PM QM RM


    【制約】
    2 <= N <= 100 : 製品の種類数
    1 <= M <= 1500 : 製造方法の数
    1 <= Pi < N : 材料の製品番号
    1 <= Qi <= 100 : 材料の個数
    1 <= Ri <= N : 製造する製品番号

    1 <= i <= M
    i ≠ j ならば (Pi,Ri) ≠ (Pj,Rj)
    すべてのRiについて、
    Riの材料(および材料の材料、…)としてRi自身を必要とすることはありません。

    【出力】
    S_1 : 製品番号1 の購入数
    S_2 : 製品番号2 の購入数
    ...
    S_N-1 : 製品番号N-1 の購入数
    : 0 <= S_i <= 4294967295 (2^32-1), 1 <= i < N

    となるようにN-1行出力してください。

    【sample1】
    2
    1
    1 5 2

    【ans1】
    5




    ⇒ 製造方法の数は1つだけで、最終製品(番号2)を作るためには、
    中間素材(番号1)の材料が5個必要です。
    番号1は製造できないので、これを5個購入すると出力すれば正解です。


    【sample2】
    4
    3
    1 1 2
    2 3 4
    3 1 4

    【ans2】
    3
    0
    1





    ⇒ 最終製品(番号4)を作るためには、製品2が3個と、製品3が1個必要になります。
    製品2は製品1から製造できるので、最終的に 製品1が3個と製品3が1個必要となります。
    購入しない製品は0を出力する必要があります。


    【sample3】
    9
    10
    1 11 2
    7 12 8
    8 13 1
    2 14 9
    8 15 9
    8 16 4
    3 17 4
    4 18 5
    5 19 9
    2 20 4

    【ans3】
    0
    0
    5814
    0
    0
    0
    11827308
    0





    提出はこちら
    http://yukicoder.me/problems/a14e51c14f78a730
    広告
    コメントを書く
    コメントをするには、
    ログインして下さい。