极简主义懒得美化
主要提供一种新做法。
我们想一想:
对于每个点,如果在某个点卖出,那就要求得能到达它的点中买入的最小花费。
由此可以用spfa慢慢拓展,spfa中d[]就不是最短路径长度了,而是路径最小值了。
具体操作:
开始先将d[]初始化为这个点买入卖出的价格(设为val[]),n个点都入队准备去拓展。
for(int i=1;i<=n;i++)
{
d[i]=val[i]=read();
q.push(i);v[i]=true;
}
然后跑spfa,求得d[]。
while(!q.empty())
{
int x=q.front();
q.pop();
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(d[y]>d[x])
{
d[y]=d[x];
if(!v[y])
{
v[y]=true;
q.push(y);
}
}
}
v[x]=false;
}
最后枚举每个点,也就是算在这里卖出获益的最大值,求max(val[i]-d[i])(1<=i<=n)就行了。
int ans=0;
for(int i=1;i<=n;i++)if(v[i])ans=max(ans,val[i]-d[i]);
真的行了吗?
回顾题面:
“阿龙决定从 1 号城市出发,并最终在 n 号城市结束自己的旅行。”
也就是说卖完后要回到点n,然而题目并没有保证所有点都能去到点n!
而且不是所有边都是无向边。
所以我们要知道哪些点不能去到点n,
可以反向建图,在这张图以n为起点看能到达哪些点。
具体做法:
v[]表示n在第二张图能到达的点,true为能到达,false为不能到达,开始先初始化为false。
n先入队,v[n]记为true。
每次取出队头,枚举以它为起点的边,如果边的终点(设为y),v[y]为false,
则v[y]标记为true,并把它入队准备去拓展。
因为点n能达到这个y,所以y能到达的点,n也能到达。
队列为空就完成了。
因为是反向建图,n能到达的点就是原图中能到达n的点了。
(这里代码和spfa的很像呢~)
q.push(n);
v[n]=true;
while(!q.empty())
{
int x=q.front();
q.pop();
for(int k=last[x][1];k;k=a[k][1].next)//[0]是原图
{
int y=a[k][1].y;
if(!v[y])
{
v[y]=true;
q.push(y);
}
}
}
在这些点求得答案即可~
int ans=0;
for(int i=1;i<=n;i++)if(v[i])ans=mymax(ans,val[i]-d[i]);
(有错误望纠正,因为不是主流思路。)
建议可以贴下完整代码
懒得贴啦
千古神犇LKY,扑通扑通跪下来~QWQ
大佬方法比y总的好懂多了ORZ
千古神犇LKY,扑通扑通跪下来~QWQ
就是这里想了好久没想懂,恍然大悟,感谢🙏
不用谢,能帮上忙我很开心
千古神犇LKY,扑通扑通跪下来~QWQ
千古神犇LKY,扑通扑通跪下来~QWQ
千古神犇LKY,扑通扑通跪下来~QWQ
千古神犇LKY,扑通扑通跪下来~QWQ
千古神犇LKY,扑通扑通跪下来~QWQ
千古神犇LKY,扑通扑通跪下来~QWQ
千古神犇LKY,扑通扑通跪下来~QWQ
千古神犇LKY,扑通扑通跪下来~QWQ
千古神犇LKY,扑通扑通跪下来~QWQ
千古神犇LKY,扑通扑通跪下来~QWQ
千古神犇LKY,扑通扑通跪下来~QWQ