【学习笔记】[CCO2021] Travelling Merchant

不难看出，这是一道在图上$DP$的问题。设$f_i$表示从$i$出发，能够不停的游走下去，所需要的最少的初始资产。可以写出粗略的转移：$f_u=\min (f_u,\max (f_v-p_i,r_i))$。

一个粗略的想法是，我们找出所有的环，然后跑$\text{spfa}$。但是找环需要枚举环上的一个点，难以优化。

我们能想到的比较高效的找环方式是拓扑排序（在这道题目中，拓扑排序的主要用途是帮助我们删掉出度为$0$的点，从而找到所有的环）。因此，考虑删掉所有出度为$0$的点，此时每个点都至少在一个环中，因此$f_u$的初值是$r_{max}$。（事实上，我们甚至可以通过拓扑排序找到包含节点$u$的所有环中$r_{max}$的最小值，这一点后面会提到）。

考虑如何求出$f_u$。我们用一个队列维护已经确定的所有的$f_u$，每次在图中找到$r_i$最大的边$(u,v,r,p)$，如果$f_v$的值已经确定了，那么用$f_v$去更新$f_u$；否则，我们发现$r$恰好是环上边的最大值（因为$v$还没有入队），可以直接用$r$去更新$f_u$。然后我们将这条最大的边从图中删去，将出度为$0$的点加入队列即可。注意每次操作完要将队列清空（保证每个点至少在一个环中）。

仔细思考这个过程，事实上和通过拓扑排序找到所有$f_u$的初值（包含$u$的所有环中$r_{max}$的最小值），然后跑$\text{spfa}$等价。（当然$\text{spfa}$更慢）

复杂度$O(m\log m)$。瓶颈在于排序。

考场上居然没想到用拓扑排序找环。。。可能还是因为惯性思维，因为不是$DAG$所以没想到拓扑排序吧。

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
const int N=2e5+5;
int n,m,du[N],vs[N];
struct node{int u,v,r,p;bool operator <(const node &a)const{return r>a.r;}
}e[N];
ll f[N];
queue<int>Q;
vector<int>G[N];
void chmin(ll &x,ll y){x=min(x,y);
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1;i<=m;i++){cin>>e[i].u>>e[i].v>>e[i].r>>e[i].p;}sort(e+1,e+1+m);for(int i=1;i<=m;i++){G[e[i].v].pb(i),du[e[i].u]++;}memset(f,0x3f,sizeof f);for(int i=1;i<=n;i++)if(du[i]==0)Q.push(i);for(int i=1;i<=m;i++){while(Q.size()){int u=Q.front();Q.pop();for(auto id:G[u]){if(vs[id])continue;int v=e[id].u;if(f[u]!=inf)chmin(f[v],max(f[u]-e[id].p,1ll*e[id].r));vs[id]=1;if(--du[v]==0)Q.push(v);}}if(!vs[i]){vs[i]=1;chmin(f[e[i].u],e[i].r);if(--du[e[i].u]==0)Q.push(e[i].u);}}for(int i=1;i<=n;i++)cout<<(f[i]==inf?-1:f[i])<<" ";
}