深基上给的代码是建正向边,就是一件任务的准备工作指向这个任务,但是从它的分析来看好像应该要建反向边,从这个任务上溯到第一件任务。
于是我把书上的代码改了改,仅仅是把linker[y].push_back(x)改为了linker[x].push_back(y),发现这样也能通过。希望有大佬能告诉我这是什么原理,谢谢。 贴上《深基》的代码:
#include<iostream>
#include<vector>
using namespace std;
int vis[10010],len[10010];
vector<int> linker[100];
int n,ans;
int dfs(int x) {
if (vis[x]) return vis[x];
for (int i = 0; i < linker[x].size(); i++)
vis[x] = max(vis[x], dfs(linker[x][i]));
vis[x] += len[x];
return vis[x];
}
int main(){
int x,y;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> x >> len[i];
while (cin >> y)
if (!y) break; else linker[y].push_back(x);
}
for (int i = 1; i <= n; i++)
ans = max(ans, dfs(i));
printf("%d",ans);
}