2012-08-14 18:04:45Morris
[ZJ][拓樸] a454: TOI2010 第二題：專案時程
內容 ：
通常在開發一個專案時，整個專案會被
分割為許多個項目，並同時分配給多組程式設計師去開發。但這些項目是有順序關係的，只有當順序在前方的項目完成後，才能夠開始開發順序在後方的項目。我們
利用一個有向圖，來表示這些項目的開發順序。圖上的每一個節點代表一個項目，節點內的數字為節點編號，上方的數字代表開發這個項目所需的天數；圖上的邊則
表示開發的順序，以右圖為例，只有在節點 2 完成後，才能夠開始節點 4 的開發。右圖為範例測試資料中的第二組專案有向圖。
有一間軟體公司目前正有許多的專案準備開始開發，但是這間公司的前一任專案管理人(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
提示
：
2 共有兩組專案測試資料時限仿照原題，更改為10秒。 (2012/7/6 修改)
2 第一組專案有兩個工作項目（節點）
8 1 2 第一個工作項目需要8天才能完成，有ㄧ個工作項目（第二個工作項目）需等第一個工作項目完成後才能進行。
2 0 第二個工作項目需要2天才能完成
5 第二組專案有五個工作項目（節點）
6 2 2 3 第一個工作項目需要6天才能完成，有兩個工作項目（第二、三個工作項目）需等第一個工作項目完成後才能進行。
5 1 4 第二個工作項目需要5天才能完成，有ㄧ個工作項目（第四個工作項目）需等第二個工作項目完成後才能進行。
11 1 5 第三個工作項目需要11天才能完成，有ㄧ個工作項目（第五個工作項目）需等第三個工作項目完成後才能進行。
4 1 5 第四個工作項目需要4天才能完成，有ㄧ個工作項目（第五個工作項目）需等第四個工作項目完成後才能進行。
8 0 第五個工作項目需要8天才能完成
出處
：
2010 TOI 研習營初選
(管理：longbiau)
#include <stdio.h>
#include <vector>
using namespace std;
int main() {
int t, n, m;
int i, x;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
int day[n+1], indeg[1001] = {};
vector<int> g[n+1], b[n+1];
for(i = 1; i <= n; i++) {
scanf("%d %d", &day[i], &m);
while(m--) {
scanf("%d", &x);
indeg[x]++;
g[i].push_back(x);
b[x].push_back(i);
}
}
int ac[1001] = {}, used[1001] = {}, flag = 1;
do {
flag = 0;
for(i = 1; i <= n; i++) {
if(indeg[i] <= 0 && used[i] == 0) {
used[i] = 1;
for(vector<int>::iterator it = b[i].begin();
it != b[i].end(); it++) {
ac[i] = ac[i] > ac[*it] ? ac[i] : ac[*it];
}
ac[i] += day[i];
for(vector<int>::iterator it = g[i].begin();
it != g[i].end(); it++) {
indeg[*it]--;
}
flag = 1;
}
}
} while(flag);
int ans = 0;
for(i = 1; i <= n; i++)
ans = ans > ac[i] ? ans : ac[i];
printf("%d\n", ans);
}
return 0;
}
#include <stdio.h>
#include <vector>
using namespace std;
int main() {
int t, n, m;
int i, x;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
int day[n+1], indeg[1001] = {};
vector<int> g[n+1], b[n+1];
for(i = 1; i <= n; i++) {
scanf("%d %d", &day[i], &m);
while(m--) {
scanf("%d", &x);
indeg[x]++;
g[i].push_back(x);
b[x].push_back(i);
}
}
int ac[1001] = {}, used[1001] = {}, flag = 1;
do {
flag = 0;
for(i = 1; i <= n; i++) {
if(indeg[i] <= 0 && used[i] == 0) {
used[i] = 1;
for(vector<int>::iterator it = b[i].begin();
it != b[i].end(); it++) {
ac[i] = ac[i] > ac[*it] ? ac[i] : ac[*it];
}
ac[i] += day[i];
for(vector<int>::iterator it = g[i].begin();
it != g[i].end(); it++) {
indeg[*it]--;
}
flag = 1;
}
}
} while(flag);
int ans = 0;
for(i = 1; i <= n; i++)
ans = ans > ac[i] ? ans : ac[i];
printf("%d\n", ans);
}
return 0;
}