UVa00452 Project Scheduling

題目連結

---

• ❗️ 題意
  給定點、經過這個點的cost、哪些點連到這個點，求出需要多少時間才能夠走完所有點。

---

• ✔️ 題解
  ans[now]代表目前這個點的答案，而ans[next]是now這個點所可以走到的點，而更新公式就是ans[next] = max(ans[next], node[next] + ans[now])，其中node是原本點上的值。
  我們只需要在利用BFS做拓墣排序的過程中更新ans的值，就能夠確定點的更新順序是對的，不會有更新點的時候前面的點還沒有更新到的問題，最後只需要輸出最大的ans[i]即可。

---

• 💻 程式碼

  140ms

  #include <bits/stdc++.h>
  using namespace std;
  
  const int MAXN = 30;
  int node[MAXN];
  int cnt[MAXN];
  int ans[MAXN];
  bool used[MAXN];
  vector<int>G[MAXN];
  
  void init(){
  	memset(node, 0, sizeof(node));
  	memset(cnt, 0, sizeof(cnt));
  	memset(ans, 0, sizeof(ans));
  	memset(used, 0, sizeof(used));
  	for(int i = 0; i < MAXN; i++){
  		G[i].clear();
  	}
  }
  
  int main(){
  	int t;
  	string line;
  	cin >> t;
  	cin.ignore();
  	getline(cin, line);
  	while(t--){
  		init();
  		while(true){
  			line.clear();
  			getline(cin, line);
  			if(line.size() == 0){
  				break;
  			}
  			stringstream ss(line);
  			char idx, another;
  			int val;
  			ss >> idx;
  			ss >> val;
  			node[idx - 'A'] = val;
  			ans[idx - 'A'] = val;
  			used[idx - 'A'] = 1;
  			while(ss >> another){
  				cnt[idx - 'A']++;
  				G[another - 'A'].emplace_back(idx - 'A');
  			}
  		}
  		queue<int>q;
  		for(int i = 0; i < MAXN; i++){
  			if(cnt[i] == 0 && used[i]){
  				q.emplace(i);
  			}
  		}
  		while(!q.empty()){
  			int now = q.front();	q.pop();
  			for(auto next: G[now]){
  				ans[next] = max(ans[next], node[next] + ans[now]);
  				cnt[next]--;
  				if(cnt[next] == 0){
  					q.emplace(next);
  				}
  			}
  		}
  		int res = 0;
  		for(int i = 0; i < MAXN; i++){
  			res = max(res, ans[i]);
  		}
  		cout << res << '\n';
  		if(t){
  			cout << '\n';
  		}
  	}
  }

  這題更煩的反而是格式輸入輸出吧…😅

---

• 🧠 心得
  當初會解這題是因為剛好有學長來問我類似的題目，也趁這次機會來複習一下拓墣排序。之前的我都是用DFS的順序來找order，而改用queue的方法只需要用一個array來記錄入in degree即可，比我用DFS的做法好寫很多。
  順帶一提，學長說這是他們進碩班老師拿給他們練習的大一題目，大一就在拓墣排序，沒搞錯吧？

---