我的方法好像和大家都不一样?
查看原帖
我的方法好像和大家都不一样?
1026751
Lawrenceling楼主2024/8/2 21:20

其实没有不一样啦,只是思路不太一样而已。

看到这道题,想了一下,想出一个性质:
对于在AOV网中的某个点,以此点做终点的最长路 的起点一定是某个入度为零的点。

说人话就是以无前驱点作起点跑最长路划算。

然后在想怎么跑DFS。。。
起初想的是每个无前驱点都跑一次,想到这里评测机已经瑟瑟发抖了。

“可以设一个 00 点,把所有无前驱点变成它的出度就好了啊!”直接开干。

代码片段(违规紫衫):

for(int i=1;i<=m;++i)
{
	int x,y;
	scanf("%d%d",&x,&y);
	v[x].push_back(y);
	ip[y]++;//入度个数
}
for(int i=1;i<=n;++i)
{
	if(ip[i]==0)
	{
		v[0].push_back(i);
	}
}
memset(dis,-0x3f,sizeof(dis));
dis[0]=0;
DFS(0);
2024/8/2 21:20
加载中...