洛谷P6145 [USACO20FEB]Timeline G 题解

题目链接：P6145 [USACO20FEB]Timeline G

题意：

Bessie 在过去的 $M$ 天内参加了 $N$ 次挤奶。但她已经忘了她每次挤奶是在哪个时候了。

对于第 $i$ 次挤奶，Bessie 记得它不早于第 $S_i$ 天进行。另外，她还有 $C$ 条记忆，每条记忆形如一个三元组 $(a,b,x)$，含义是第 $b$ 次挤奶在第 $a$ 次挤奶结束至少 $x$ 天后进行。

现在请你帮 Bessie 算出在满足所有条件的前提下，每次挤奶的最早日期。

保证 Bessie 的记忆没有错误，这意味着一定存在一种合法的方案，使得：

• 第 $i$ 次挤奶不早于第 $S_i$ 天进行，且不晚于第 $M$ 天进行；
• 所有的记忆都得到满足；

输入格式：

第一行三个整数 $N,M,C$。保证 $1 \leq N,C \leq 10^5$，$2 \leq M \leq 10^9$。

接下来一行包含 $N$ 个整数 $S_1, S_2 , \ldots, S_n$，保证 $\forall 1 \leq i \leq n$，都满足 $1 \leq S_i \leq M$。

下面 $C$ 行每行三个整数 $a,b,x$，描述一条记忆。保证 $a \neq b$，且 $1 \leq x \leq M$。

输出格式：

输出 $N$ 行，每行一个整数，第 $i$ 行的数表示第 $i$ 次挤奶的最早日期。

对于 $b - a \ge c$ ，移项可得 $a + c \le b$ 。

然后我们连一条有向边 $a \to b$ ，跑一遍最长路就能得到了。每个结点的最长路初始值就是给的 $S_i$ 。

因为题目保证有解，所以这张图一定是个 DAG ，我们直接跑一遍 $\mathtt{topo_sort}$ 就好了

注意这里有一个常见误区。为什么我们不把它变成 $b + c \ge a$ ，连 $b \to a$ ，边权为 $c$ 然后跑最短路呢？

因为题目给出了 $S$ ，而 $S_i$ 的含义为 $a \ge S_a$ 。如果我们以 $S_b$ 为 $b$ 的初值去跑，可能无法满足 $a \ge S_a$ 。

从逻辑上说，我们并不知道每个结点的真实值，我们只知道他们的下界。

那么我们做的其实就是把这个过程反过来，从 $a$ 跑到 $b$ ，也就是正解的连边。

时间复杂度 $\mathcal{O}(n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5+15))

int n,m,c,pos=1,head[N],in[N],f[N];
struct Edge { int u,v,w,next; } e[N];
void addEdge(int u,int v,int w)
{ e[++pos] = {u,v,w,head[u]}; head[u] = pos; ++in[v]; }
queue<int> q;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m >> c;
    for(int i=1; i<=n; i++) cin >> f[i];
    for(int i=1,u,v,w; i<=c; i++)
    {
        cin >> u >> v >> w;
        addEdge(u,v,w);
    }
    for(int i=1; i<=n; i++) if(!in[i]) q.push(i);
    
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        for(int i=head[u]; i; i=e[i].next)
        {
            int v = e[i].v;
            up(f[v], f[u] + e[i].w);
            if(!(--in[v])) q.push(v);
        }
    }
    for(int i=1; i<=n; i++) cout << f[i] << '\n';
    return 0;
}