おもちゃを組み立てる

おもちゃを組み立てる

アイデア

最初に入る回数のないノードが基本です.基本部品から総コストを記録します.キューに入れて回転し、入力回数が0の場合は、自分の作成に必要なすべての部品を考慮してキューに入れます.総原価計算方法は以下の通りです.

while (!q.empty()) {
    int cur = q.front();
    q.pop();
    for (auto p : adj[cur]) {
        int next = p.first;
        int cnt = p.second;
        for (int i = 1; i < N+1; i++) {
            tc[i][next] += tc[i][cur]*cnt;
        }
        if (!(--indegree[next])) {
            q.push(next);
        }
    }
}

curでnextを作成するために必要なすべての部品は、iを使用してcurを作成するために必要な部品の数*curでnextを作成するために必要な部品の数です.
1番部品からN番部品まですべて記録し、2つの基本部品だけを出力すればよい.

コード#コード#

#include <bits/stdc++.h>

using namespace std;

constexpr int MAX = 101;
int N, M;
int indegree[MAX], tc[MAX][MAX];
bool b[MAX];
vector<vector<pair<int, int>>> adj;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;
    adj = vector<vector<pair<int, int>>>(N+1);
    while (M--) {
        int x, y, k;
        cin >> x >> y >> k;
        adj[y].push_back({x, k}); // k개의 x가 필요하다.
        indegree[x]++;
    }

    queue<int> q;
    for (int i = 1; i < N+1; i++) {
        if (!indegree[i]) {
            q.push(i);
            b[i] = true;
            tc[i][i] = 1;
        } 
    }

    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (auto p : adj[cur]) {
            int next = p.first;
            int cnt = p.second;
            for (int i = 1; i < N+1; i++) {
                tc[i][next] += tc[i][cur]*cnt;
            }
            if (!(--indegree[next])) {
                q.push(next);
            }
        }
    }

    for (int i = 1; i < N+1; i++) {
        if (tc[i][N] && b[i]) {
            cout << i << ' ' << tc[i][N] << '\n';
        }
    }

    return 0;
}

おしゃべり

一度に計算出力すればいいのですが、完成品を作るために必要な部品を見つけて、そこで逆方向に追跡してMLEを手に入れました.