洛谷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;
}