67 lines
1.9 KiB
C++
67 lines
1.9 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
const int N = 10010;
|
||
int n; //必须完成的杂务的数目
|
||
int x; //工作序号
|
||
int y; //一些必须完成的准备工作
|
||
int ans; //最终结果
|
||
int a[N]; //完成工作所需要的时间a[x]
|
||
int f[N]; //这个结点的最长时间
|
||
vector<int> edge[N]; //出边链表
|
||
int ind[N]; //入度
|
||
queue<int> q; //队列
|
||
/**
|
||
测试数据：
|
||
7
|
||
1 5 0
|
||
2 2 1 0
|
||
3 3 2 0
|
||
4 6 1 0
|
||
5 1 2 4 0
|
||
6 8 2 4 0
|
||
7 4 3 5 6 0
|
||
|
||
答案：
|
||
23
|
||
*/
|
||
|
||
int main() {
|
||
//需要完成的杂务的数目
|
||
cin >> n;
|
||
//创建DAG
|
||
for (int i = 1; i <= n; i++) {
|
||
cin >> x >> a[x];
|
||
while (cin >> y) {
|
||
if (!y) break;
|
||
//y是前序结点
|
||
edge[y].push_back(x);//y结点出发到达x结点的边，所以x结点的入度++
|
||
ind[x]++;//维护入度
|
||
}
|
||
}
|
||
//步骤一:初始化队列，将入度为 0 的节点放入队列。
|
||
for (int i = 1; i <= n; i++) {
|
||
if (ind[i] == 0) {//如果入度为0，则为DAG的入口
|
||
q.push(i);//入队列
|
||
f[i] = a[i];//初始值,动态规划的base case
|
||
}
|
||
};
|
||
//拓扑排序
|
||
while (!q.empty()) {
|
||
int p = q.front();
|
||
q.pop();
|
||
//步骤二:取出队首，遍历其出边，删除出边，将能够到达的点入度减一，同时维护答案数组。
|
||
for (int i = 0; i < edge[p].size(); i++) {
|
||
int y = edge[p][i];
|
||
ind[y]--;
|
||
if (ind[y] == 0) q.push(y); //步骤三:若在此时一个点的入度变为 0，那么将其加入队列。
|
||
//看看能不能获取到更大的时长
|
||
f[y] = max(f[y], f[p] + a[y]);
|
||
}
|
||
}
|
||
//统计答案
|
||
for (int i = 1; i <= n; i++) ans = max(ans, f[i]);
|
||
//输出大吉
|
||
printf("%d\n", ans);
|
||
return 0;
|
||
} |