P7831 [CCO 2021] Travelling Merchant 的题解

· · 题解

考察：图上环形 DP。

这是一种神秘的贪心优化 DP trick。

设点 u 的答案为 dp_u，对于相邻点 v，有方程：

dp_u = \displaystyle\min_{v}\max\{r_{u,v},dp_v - p_{u,v}\}

可以发现这是一类 DP 方程带环的问题。

换一种思路，考虑对每一个 dp_u 的值设计一个上界，借此断掉其中的环，然后通过朴素的拓扑排序精确到确切值。

考虑到在行走的整个过程中，我们的资产是不降的。或者说，观察转移方程，dp_u \le r_{max} 总成立。也就是说，对于一个 r_{max} 我们可以使用它直接转移此边，回顾拓扑排序的内涵，这条边完成了其连接两点间的转移，也就完成了它在拓扑排序中的任务，可以删去。

考虑拓扑排序的过程，处理掉环之外的部分后，发现实质上当前任意一点均可以到达一个环。假设当前全局 r_{max} 所在边为 u\rarr v，此时设 dp_u 上界为 r_{max} 必然保证其可以在整个图上任意一边顺利通行，也就必然可以到达一个环，故此时的操作合法。此时一条边已经被断掉，多出了部分 DAG，继续使用拓扑排序正常转移掉非环部分。然后继续查找全局 r_{max}，重复过程。

我们发现这样的算法能够计算到所有点，且完美处理的 DP 转移带环的问题。时间复杂度 \mathcal{O}(m\log m + n + m)，相当优秀。

总体来说，这个 trick 就是通过题目中的一些全局信息，确定局部 DP 上界，断掉环之后可继续转移，遇到环再断，最终将答案精确到确切数值。

好题好题。

::::success[代码]

#include<bits/stdc++.h>
#define endl '\n'
//#define MSOD

using namespace std;
using ll = long long;

constexpr ll N = 2e5 + 5;

bool vis[N];
ll n, m;
ll in[N], ans[N];
struct E {
    ll u, v, r, p, id;
    inline friend bool operator < (E x, E y) {
        return x.r > y.r;
    }
} edg[N];
struct T {
    ll v, r, p, id;
    T(ll x, ll y, ll z, ll w) : v(x), r(y), p(z), id(w) {}

};
vector<T> g[N];
inline void solve() {
    cin>>n>>m;
    for(int i = 1 ; i <= m ; i ++) {
        cin>>edg[i].u>>edg[i].v>>edg[i].r>>edg[i].p;
        edg[i].id = i;
        g[edg[i].v].push_back(T(edg[i].u, edg[i].r, edg[i].p, edg[i].id));
        in[edg[i].u] ++;
    }
    sort(edg + 1, edg + m + 1);
    fill(ans + 1, ans + n + 1, LLONG_MAX);
    queue<ll> q;
    for(int i = 1 ; i <= n ; i ++) {
        if(!in[i]) {
            q.push(i);
        }
    }
    for(int i = 1 ; i <= m ; i ++) {
        while(!q.empty()) {
            ll u = q.front();
            q.pop();
            for(auto i : g[u]) {
                ll v = i.v, r = i.r, p = i.p, id = i.id;
                if(vis[id]) {
                    continue;
                }
                vis[id] = true;
                if(ans[u] != LLONG_MAX) {
                    ans[v] = min(ans[v], max(ans[u] - p, r));
                }
                if((-- in[v]) == 0) {
                    q.push(v);
                }
            }
        }
        if(!vis[edg[i].id]) {
            vis[edg[i].id] = true;
            ans[edg[i].u] = min(ans[edg[i].u], edg[i].r);
            if((-- in[edg[i].u]) == 0) {
                q.push(edg[i].u);
            }
        }
    }
    for(int i = 1 ; i <= n ; i ++) {
        cout<<(ans[i] == LLONG_MAX ? -1 : ans[i])<<" \n"[i == n];
    }
    return;
}

signed main() {
    ios::sync_with_stdio(false), cout.tie(0), cin.tie(0);
    int TC = 1;
#ifdef MSOD
    cin>>TC;
#endif
    while(TC --) {
        solve();
    }
    return 0;
}

::::