一点建图上的疑问
  • 板块P1113 杂务
  • 楼主liysjianttso
  • 当前回复4
  • 已保存回复4
  • 发布时间2023/6/11 14:30
  • 上次更新2023/10/23 13:22:45
查看原帖
一点建图上的疑问
538085
liysjianttso楼主2023/6/11 14:30

深基上给的代码是建正向边,就是一件任务的准备工作指向这个任务,但是从它的分析来看好像应该要建反向边,从这个任务上溯到第一件任务。

于是我把书上的代码改了改,仅仅是把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);
}
2023/6/11 14:30
加载中...