P7831 [CCO2021] Travelling Merchant 题解

· · 题解

货真价实的好题。

如果定义 f_u 表示从 u 出发能不停走下去的最少初始资产，很容易得到一个这样的转移：f_u = \min\limits_{(u, v) \in E}\{f_u,\max(r(u, v), f_v - p(u, v))\}。但是图上有环，不能直接转移。我们尝试发现一些性质：

  1. 如果你从某点开始走，初始资产为所有边 r 的最大值，那你自然可以畅行无阻。
  2. 出度为 0 的点一定无解。由此得出形如 (u, v) 的边若 v 出度为 0，则该边没有意义，可以删去。

综合以上两个性质得出做法：

  1. 将所有出度为 0 的节点入队。
  2. 按 r 从大到小的顺序考虑每条边。首先进行一次“拓扑排序”。具体来说，取出队头 v，遍历 v 在反图上的出边 (v, u, r, p)。若 v 有解，则用最开始提到的转移式子来更新 f_u。因为此时 v 已经入队，f_v 已经确定，所以可以用这条边更新。同时，这条边被使用之后不再具有价值，可以退出历史的舞台。删去这条边之后把 u 的出度 -1，若 u 的出度变为 0 则将其入队。
  3. 从大到小考虑第 i 条边时：做完第二步之后，若第 i 条边仍未被删除则用 r_i 更新 f_{u_i}，并将 u_i 的出度 -1，若变为 0 则将其入队。为啥可以这样更新呢？我们发现一条边被删除，当且仅当沿着这条边最终会走到出度为 0 的点，也就是无解。所以如果第 i 条边未被删除则代表着“在未被删除的边构成的图上，沿着第 i 条边并不会走到出度为 0 的点”，同时边是按 r 从大到小的顺序考虑的，以 r_i 为初始资产不会受到未被删除的边的 r 的限制。所以此时可以更新。
  4. 第 3 步使得每个节点最终都会入队，解决了一开始“有环就无法转移”的问题。

由于拓扑排序中每个节点只会入队出队各一次，所以复杂度瓶颈在排序：O(m \log m)。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 2e5 + 5, inf = 0x3f3f3f3f;
int n, m, out[N];
struct Edge{
    int u, v, id, r, p;
    bool operator < (const Edge &k) const {
        return r > k.r;
    }
}E[N];
bool vis[N];
int head[N], cnt;
struct edge{
    int nxt, to, id, r, p;
}e[N << 1];
void add(int u, int v, int id, int r, int p){
    e[++cnt].nxt = head[u], e[cnt].to = v, e[cnt].id = id, e[cnt].r = r, e[cnt].p = p, head[u] = cnt;
}
int ans[N];
queue <int> q;
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i++) scanf("%d%d%d%d", &E[i].u, &E[i].v, &E[i].r, &E[i].p), E[i].id = i, add(E[i].v, E[i].u, E[i].id, E[i].r, E[i].p), out[E[i].u]++;
    memset(ans, 0x3f, sizeof(ans));
    for(int i = 1; i <= n; i++) if(!out[i]) q.push(i);
    sort(E + 1, E + m + 1);
    for(int i = 1; i <= m; i++){
        while(!q.empty()){
            int v = q.front(); q.pop();
            for(int i = head[v]; i; i = e[i].nxt){
                if(vis[e[i].id]) continue;
                vis[e[i].id] = true;
                int u = e[i].to;
                if(ans[v] != inf) ans[u] = min(ans[u], max(e[i].r, ans[v] - e[i].p));
                out[u]--; if(!out[u]) q.push(u);
            }
        }
        if(!vis[E[i].id]){
            vis[E[i].id] = true, ans[E[i].u] = min(ans[E[i].u], E[i].r);
            out[E[i].u]--; if(!out[E[i].u]) q.push(E[i].u);
        }
    }
    for(int i = 1; i <= n; i++) printf("%d ", ans[i] == inf ? -1 : ans[i]);
    return 0;
}