[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;
}