P7831 [CCO2021] Travelling Merchant CWOI1113B

首先将边反向，再按 \(r\) 从大到小排序，这样可以使得答案的转移没有后效性。
令 \(ans_i\) 表示 \(i\) 这个点最少有多少资产方能无限地走下去。（初值为 \(inf\) ）
依次枚举每一条边。（令 \(u\) 为这条边的起点，\(v\) 为这条边的终点）

• 首先对现在的图进行一遍 topo ，转移方程为 \(ans_v=min(ans_v,max(r,ans_u-p))\)(要求 \(ans_u\) 不为 \(inf\)) ，因为如果只考虑当前这条边的话，\(v\) 点的资产至少要为 \(r\) 才能走出去，而且必须要使走过这条边后的资产 \(\ge ans_u\) ，于是有了上面的方程。走过的边都要删掉。
• 更新 \(ans_u=min(ans_u,r)\) ，删掉这条边，若点 \(u\) 入度为 \(0\) 则加入队列。

手动模拟一下这个过程，可以发现一个环的答案只会对后面的点有贡献，因此可以求出答案为 \(-1\) 的点。

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=2e5+5,inf=1e18;
int n,m,ans[N],d[N];
struct edge{
    int u,v,r,p;
    edge(){}
    edge(int u,int v,int r,int p):u(u),v(v),r(r),p(p){}
}e[N];
bool vis[N];
vector<int> g[N];

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for (int i=1;i<=m;i++)
    {
        int u,v,r,p;
        cin>>u>>v>>r>>p;
        e[i]=edge(u,v,r,p);
    }
    for (int i=1;i<=n;i++) ans[i]=inf;
    sort(e+1,e+1+m,[&](edge a,edge b){return a.r>b.r;});
    for (int i=1;i<=m;i++) g[e[i].v].emplace_back(i),d[e[i].u]++;
    queue<int> q;
    for (int i=1;i<=n;i++) if (!d[i]) q.push(i);
    for (int i=1;i<=m;i++)
    {
        while (!q.empty())
        {
            int u=q.front();
            q.pop();
            for (int nex:g[u])
            {
                if (vis[nex]) continue;
                vis[nex]=1;
                int v=e[nex].u;
                d[v]--;
                if (ans[u]!=inf) ans[v]=min(ans[v],max(e[nex].r,ans[u]-e[nex].p));
                if (!d[v]) q.push(v);
            }
        }
        if (vis[i]) continue;
        auto& [u,v,r,p]=e[i];
        vis[i]=1;
        d[u]--;
        ans[u]=min(ans[u],e[i].r);
        if (!d[u]) q.push(u);
    }
    for (int i=1;i<=n;i++) cout<<(ans[i]==inf?-1:ans[i])<<' ';
}

最难的部分在于想到从大到小贪心。