ZeroJudge A454: Project Timeline

Typically, when developing a project, the entire project is divided into many tasks, and these tasks are simultaneously assigned to multiple groups of programmers to develop. However, these tasks have a sequential relationship, meaning that only when a task earlier in the sequence is completed can development of the subsequent task begin. We use a directed graph to represent the development sequence of these tasks. Each node in the graph represents a task, with the number inside the node being the task's identifier, and the number above the node representing the number of days required to develop this task. The edges in the graph indicate the development order. For example, in the below diagram, task 4 can only start after task 2 is completed. The below diagram is the directed graph for the second set of project test data in the example.

A software company currently has many projects ready to start development. However, the previous project manager (PM) left due to the pressure, leaving behind a preliminary development flowchart. Now, you are the new project manager of this company, and your boss urgently wants to know if these projects can be completed within the time limits he has set. Please write a program that, based on these development flowcharts, answers your boss's question.

Sample Inputs/Outputs

Thought Process

Store the number of days required for each node, all preceding nodes, and all succeeding nodes. Also, declare a variable answer initialized to 0.

使用 DFS，需要的參數有目前的節點位置還有一個整數 weight 代表目前加起來所耗費的天數。每次進 DFS 時都要將 weight += 目前節點的耗費天數，並且要宣告一個 Map<int, int> ans 來存每個節點的最大耗費天數，每次都要更新 ans[目前節點]，看是 ans[目前節點] 比較大還是 weight，更新值為較大者。然後，還要更新 answer 變數至最大值，和 ans[目前節點] 比較。

跑一個 For迴圈 將目前節點的所有「後面的節點」進行判斷，如果有節點可以走，亦代表其節點前面的點都走過了，就可以再呼叫新的 DFS。這邊可以再宣告一個 Map<int, int> 來判斷哪些的點已經走過了。

Because there may be multiple graphs, calling DFS involves using a for loop to evaluate each node and then recursively calling DFS. If the current node being processed is a starting node (i.e., it has no preceding nodes), initiate DFS using this node.

The final output value should be the answer variable.

Sample Code－ZeroJudge A454: Project Timeline

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

vector<int>Day;
vector<vector<int>>go;
map<int, vector<int>>MAP;
map<int, int>walk, ans;
int answer = 0;

void DFS(const int pos, int weight) {
    const vector<int>destinations = go[pos];
    weight += Day[pos];
    ans[pos] = max(ans[pos], weight);
    answer = max(ans[pos], answer);
    for (int i = 0; i<destinations.size(); i++) {
        const int current = destinations[i];
        const vector<int> condition = MAP[current];
        bool ok = true;
        int mm = -1;
        walk[current]++;
        if (walk[current] < condition.size()) continue;
        for (int point : condition) {
            mm = max(mm,ans[point]);
        }
        DFS(current, mm);
    }
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    for (int i = 0; i<T; i++) {
        Day.clear();
        go.clear();
        MAP.clear();
        walk.clear();
        ans.clear();
        answer = 0;
        int N;
        cin >> N;
        for (int j = 0; j<N; j++) {
            int day, K;
            cin >> day >> K;
            Day.push_back(day);
            vector<int>hi;
            for (int k = 0; k<K; k++) {
                int tmp;
                cin >> tmp;
                tmp--;
                MAP[tmp].push_back(j);
                hi.push_back(tmp);
            }
            go.push_back(hi);
        }
        for(int j = 0; j < N; j++) {
            if (MAP[j].empty()) DFS(j, 0);
        }
        cout << answer << "\n";
    }
}

//ZeroJudge A454
//Dr. SeanXD