解题思路
不难看出，在所有给定的关系中存在着时间上的先后顺序，那么就会想到用拓扑排序进行求解，在拓扑排序的同时将时间线上最后完成的点记录下来。这就是答案
附上代码
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
const int maxn = 1e4+
3;
int n, t[maxn], x, indgr[maxn], cnt[maxn], dis[maxn][
103], fin[maxn], Ans;
queue<
int>
Q;
int main() {
scanf("%d", &
n);
for(
int i=
1; i<=n; i++
) {
scanf("%d", &
i);
scanf("%d", &
t[i]);
while (scanf(
"%d", &x) ==
1) {
if(x ==
0)
break;
indgr[i] ++
;
dis[x][++ cnt[x]] =
i;
}
}
for(
int i=
1; i<=n; i++
) {
if(indgr[i] ==
0) Q.push(i);
}
while (!
Q.empty()) {
x =
Q.front();
Q.pop();
fin[x] +=
t[x];
Ans = (Ans > fin[x]) ?
Ans : fin[x];
for(
int i=
1; i<=cnt[x]; i++
) {
indgr[dis[x][i]] --
;
fin[dis[x][i]] = (fin[dis[x][i]] > fin[x]) ?
fin[dis[x][i]] : fin[x];
if(indgr[dis[x][i]] ==
0) {
Q.push(dis[x][i]);
}
}
}
printf("%d", Ans);
}
转载于:https://www.cnblogs.com/bljfy/p/9463793.html
相关资源：锣鼓声声迎新春——新年工作计划ppt模板.zip
