UVA452 Project Scheduling

Graph, Topological sort(위상정렬)

출처: UVA UVA452 Project Scheduling

동일문제 BOJ: ACM Craft
SOL)
한 작업이 시작되려면 선행작업을 모두 수행해야 한다.
이 때 걸리는 시간은 선행작업 중 가장 오래 걸리는 시간이다.
그리고 해당 작업이 완료되면 고유 작업 수행시간을 더해준다.
모든 작업이 수행되는 동안 가장 오래 걸린 시간이 답이다.


[-] Collapse

#include<stdio.h>
#include<iostream>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
using namespace std;

int jobTerm[30];
int finishTime[30];
int indegree[30];
int adj[30][30];
int exist[30];
string str;
queue<int> q;

void setting(string str){
    int i = 2;
    exist[str[0] - 'A'] = true;
    while (true){
        if (i >= str.length() || str[i] == ' ') break;
        jobTerm[str[0] - 'A'] = jobTerm[str[0] - 'A'] * 10 + str[i] - '0';
        i++;
    }
    i++;
    for (; i < str.length(); i++){
        indegree[str[0] - 'A']++;
        adj[str[i] - 'A'][str[0] - 'A'] = 1;
    }
}

void init(){
    memset(jobTerm, 0, sizeof(jobTerm));
    memset(indegree, 0, sizeof(indegree));
    memset(finishTime, 0, sizeof(finishTime));
    memset(adj, 0, sizeof(adj));
    memset(exist, false, sizeof(exist));
}
void topo(){
    int task = 0;
    priority_queue<pair<int, int> >temp;
    while (!q.empty()){
        int size = q.size();
        for (int i = 0; i < size; i++){
            int here = q.front();
            q.pop();
            finishTime[here] += jobTerm[here];
            task = max(finishTime[here], task);
            for (int i = 0; i < 30; i++){
                if (adj[here][i] > 0){
                    finishTime[i] = max(finishTime[i], finishTime[here]);
                    if (--indegree[i] > 0) continue;
                    q.push(i);
                }
            }
        }
    }
    cout << task << endl;
}

int main(){
    //freopen("input.txt", "r", stdin);
    int testCase;
    bool first = true;
    cin >> testCase;
    getline(cin, str);
    getline(cin, str);
    while (testCase--){
        init();
        if (!first) cout << endl;
        first = false;
        while (getline(cin, str)){
            if (str == "") break;
            setting(str);
        }
        for (int i = 0; i < 30; i++)
        if (indegree[i] == 0 && exist[i]) q.push(i);
        topo();
    }
}