ZeroJudge A454: 專案時程

通常在開發一個專案時，整個專案會被分割為許多個項目，並同時分配給多組程式設計師去開發。但這些項目是有順序關係的，只有當順序在前方的項目完成後，才能夠開始開發順序在後方的項目。我們利用一個有向圖，來表示這些項目的開發順序。圖上的每一個節點代表一個項目，節點內的數字為節點編號，上方的數字代表開發這個項目所需的天數；圖上的邊則表示開發的順序，以右圖為例，只有在節點 2 完成後，才能夠開始節點 4 的開發。右圖為範例測試資料中的第二組專案有向圖。

ZeroJudge A454 題目解說

有一間軟體公司目前正有許多的專案準備開始開發，但是這間公司的前一任專案管理人 (PM) 因不堪壓力離職了，在臨走之前他留下了當初初略畫出的開發流程圖。現在你是這間公司新進的專案管理人，而你的老闆正迫切的想知道這些專案能不能在他所限制的時間內完工，請你寫一個程式依照這些專案的開發流程圖回答老闆的問題。

範例測資

範例輸入範例輸出
輸入的第一行有一個整數，代表後續測試資料組數。每組測試資料代表一個專案的有向圖，在每組測試資料的第一行有一個正整數N，代表這個專案共有 N 個工作事項（節點），N <= 1000。接下來有 N 行測試資料，每一行依序代表一個項目節點 (從 1 開始)，第一個正整數表示完成這個項目所需的天數，第二個正整數 K 表示這個節點有 K 條指向其他節點的邊，接下來 K 個正整數表示所指向的項目節點編號。

註：專案的有向圖不一定都會是連結在一起的。		對於每組測試資料輸出完成該專案所需的最少天數。
2
2
8 1 2
2 0
5
6 2 2 3
5 1 4
11 1 5
4 1 5
8 0		10
25
ZeroJudge A454 範例測資

解題思路

將每個節點的耗費天數、前面的全部節點、後面的全部節點存起來，並且宣告一個 answer 變數預設為 0。

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

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

因為有可能會有多個圖的情況，所以呼叫 DFS 是要用 For迴圈 將每個節點做判斷再來呼叫 DFS，如果跑到的節點是起點，亦代表其前面沒有任何節點，就使用目前這個節點來呼叫 DFS。

最後要輸出的數值為 answer 變數。

範例程式碼－ZeroJudge A454: 專案時程

#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
標籤

相關文章

發佈留言