其实没有不一样啦,只是思路不太一样而已。
看到这道题,想了一下,想出一个性质:
对于在AOV网中的某个点,以此点做终点的最长路 的起点一定是某个入度为零的点。
说人话就是以无前驱点作起点跑最长路划算。
然后在想怎么跑DFS。。。
起初想的是每个无前驱点都跑一次,想到这里评测机已经瑟瑟发抖了。
“可以设一个 0 点,把所有无前驱点变成它的出度就好了啊!”直接开干。
代码片段(违规紫衫):
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);