yukicoder No.30 - たこやき工場

問題

http://yukicoder.me/problems/no/30

解法

製品が製品の材料であるとき, からに向かって辺を張るような有向グラフを作ります.
入次数が1以上の頂点は他の材料から作ることになるので, 購入個数は0です. よって入次数0の頂点について考えます.
ここで:=(製品を作るのに必要な製品の個数)と定義します. これは頂点を始点とする辺の集合をとすると により求めることができます.
あとははメモ化をすればokです.

ソースコード

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

struct Edge {
    int to, cost;
};

typedef long long ll;

const int kMAX_N = 110;
const int kMAX_M = 1510;
ll magnifications[kMAX_N];

int N, M;
vector<Edge> graph[kMAX_N];
int deg_minus[kMAX_N];

int P[kMAX_M], R[kMAX_M];
ll Q[kMAX_M];

// 倍率を返す
ll DFS(int node) {
    if (magnifications[node] > 0) return magnifications[node];
    if (node == N - 1) return 1;
    ll mag = 0;
    for (int i = 0; i < graph[node].size(); i++) {
        Edge e = graph[node][i];
        mag += DFS(e.to) * e.cost;
    }
    return magnifications[node] = mag;
}

void Solve() {
    for (int i = 0; i < M; i++) {
        graph[P[i] - 1].push_back((Edge){R[i] - 1, Q[i]});
        deg_minus[R[i] - 1]++;
    }

    for (int i = 0; i < N - 1; i++) {
        if (deg_minus[i] == 0) {
            cout << DFS(i) * 1 << endl;
        } else {
            cout << 0 << endl;
        }
    }
}

int main() {
    cin >> N >> M;

    for (int i = 0; i < M; i++) {
        cin >> P[i] >> Q[i] >> R[i];
    }

    Solve();

    return 0;
}