[14907] 프로젝트 스케줄링

https://www.acmicpc.net/problem/14907

14907번: 프로젝트 스케줄링

입력이 귀찮은 구현(?)문제, 알파벳은 숫자로 바꿔주거나, 배열 크기를 100정도로 잡거나..

한줄 입력받고 파싱할때, 작업 전 완료해야하는 작업이 0개인 경우에 ' '(공백)이 한줄에 한번만 들어올 수 있음에 유의

---

#include <bits/stdc++.h>

using namespace std;

#ifdef ONLINE_JUDGE

constexpr bool local = false;

#else

constexpr bool local = true;

#endif

using ll = long long;

using pi = pair<ll, ll>;

vector<int> adj[26];

int cost[26], d[26], dp[26];

queue<int> q;

string s;

int main(void) {

    if (!local) ios_base::sync_with_stdio(0), cin.tie(0);

    int i;

    while (getline(cin, s)) {

        int idx = s[0] - 'A';

        auto it = find(s.begin() + 2, s.end(), ' ');

        string x = string(s.begin() + 2, it);

        cost[idx] = stoi(x);

        if (it == s.end()) continue;

        string pre = string(it + 1, s.end());

        int S = pre.length();

        d[idx] += S;

        for (i = 0; i < S; i++) adj[pre[i] - 'A'].push_back(idx);

    }

    for (i = 0; i < 26; i++)

        if (d[i] == 0 and cost[i] > 0) q.push(i), dp[i] = cost[i];

    memcpy(dp, cost, sizeof(cost));

    while (!q.empty()) {

        int cur = q.front();

        q.pop();

        for (auto& nxt : adj[cur]) {

            dp[nxt] = max(cost[nxt] + dp[cur], dp[nxt]);

            if (--d[nxt] == 0) q.push(nxt);

        }

    }

    cout << *max_element(dp, dp + 26);

    return 0;

}

---

https://www.acmicpc.net/problem/1516

위 문제와 사실상 동일한 문제