[ABC137E] Coins Respawn 题解

[ABC137E] Coins Respawn 题解

洛谷。

题目简述

给定一个 $n$ 个点，$m$ 条边的有向图，从点 1 走到点 n，若总共走了 $x$ 步，则最后需要减去 $xp$。

求是否有一个最大值，若有，输出。否则，输出 -1。

思路

先看需要减去 $xp$ 的问题。

显然每经过一条边都需要减去一个 $p$，那么不妨将每条边的权值减去 $p$。

再来看看没有答案的情况是咋样的。

显然，若图中出现了正权环，且是最长路上经过的环，则无解。

那么第一反应就是用 spfa 判正环。

再优化一下。

都知道了必须是路上经过的环，那么不如先 dfs 一遍，从 n 号点出发，因为是有向图，所以建个反图，暴力 dfs，并记录所有遇到的点。

在 spfa 中，若遇到了没有在路径上的点，则跳过，否则正常松弛操作。

AC Code

#include<bits/stdc++.h>
using namespace std;
#define ljl long long
const ljl N=2505,M=5005,inf=-1e18;
ljl n,m,p,head[N],cnt_e;
queue<ljl> q;
ljl dis[N],cnt[N];
bool vis[N],vis_in_dfs[N];
vector<ljl> vec[N];
struct E{
	ljl to,w,pre;
}e[M];
void add(ljl from,ljl to,ljl w)
{
	e[++cnt_e].to=to;
	e[cnt_e].w=w;
	e[cnt_e].pre=head[from];
	head[from]=cnt_e;
	return;
}
void dfs(ljl u)//暴力 dfs
{
	if(vis_in_dfs[u])return;
	vis_in_dfs[u]=1;
	for(auto i:vec[u])
		dfs(i);
	return;
}
bool spfa()
{
	for(ljl i=2;i<=n;++i)
		dis[i]=inf;
	q.push(1);vis[1]=1;
	while(!q.empty())
	{
		auto u=q.front();q.pop();
		vis[u]=0;
		for(ljl i=head[u];i;i=e[i].pre)
		{
			ljl v=e[i].to,w=e[i].w;
			if(!vis_in_dfs[v]) continue;//遇到了不可能在路径上的，直接跳过
			if(dis[v]<dis[u]+w)
			{
				dis[v]=dis[u]+w;
				if(!vis[v])
				{
					vis[v]=1;
					q.push(v);
					cnt[v]=cnt[u]+1;
					if(cnt[v]>=n)
						return 1;
				}
			}
		}
	}
	return 0;
}
int main(){
	ios::sync_with_stdio(0);
	cin>>n>>m>>p;
	for(ljl i=1,u,v,w;i<=m;++i)
	{
		cin>>u>>v>>w;
		add(u,v,w-p);vec[v].push_back(u);//正常的图和反图
	}
	dfs(n);
	if(spfa())
	{
		cout<<"-1\n";
		return 0;
	}
	cout<<max(0*1ll,dis[n])<<'\n';//记得和0取最大值，因为最后是扣光，而不是负债
	return 0;
}