题解 P6145 【[USACO20FEB]Timeline G】
_Fontainebleau_
·
·
题解
这道题貌似可以用拓扑做。
但是我不会。
于是就有了差分约束的做法。
不清楚差分约束的，建议去看看这道模板题，还有这道，都是差分约束的模板。
好，我们假设您已经 A 了上述两题（中的一题），那么，再看看这道题。
是不是觉得很水呢。
$2.$ 第 $b$ 次挤奶在第 $a$ 次后至少 $x$ 天进行，那么就让它在后 $x$ 天进行。
要实现 $1.$ 的建图，需要建一个**超级源点** $s$ 。
因为题目保证有解（保证 Bessie 的记忆没有错误，这意味着**一定存在一种合法的方案**），所以可以放心的跑**最长路**，不用判断正环。
于是就是代码（队列是手写的）。
------------
```cpp
#include<bits/stdc++.h>
#define FOR(i,j,k) for(int i=(j);i<=(k);i++)
using namespace std;
int n,m,c,s,cnt;
int h[100010],t[200001],nxt[200001],val[200001];
int dis[100010];
bool inq[100010];
int f,e,q[100010001];
inline int read()
{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}//快读
inline void addedge(int a,int b,int c)
{
t[++cnt]=b,val[cnt]=c,nxt[cnt]=h[a],h[a]=cnt;
}
inline void spfa()
{
while(f<=e)
{
int u=q[f++];
for(int p=h[u];p;p=nxt[p])
{
int v=t[p];
if(dis[v]<dis[u]+val[p])
{
dis[v]=dis[u]+val[p];
if(!inq[v]) inq[v]=true,q[++e]=v;
}
}
inq[u]=false;
}
return ;
}
int main()
{
memset(dis,-1,sizeof(dis));
n=read(),m=read(),c=read(),s=n+1;
for(int i=1;i<=n;i++)
{
int x=read();
addedge(s,i,x); //超级源点
}
for(int i=1;i<=c;i++)
{
int u=read(),v=read(),w=read();
addedge(u,v,w);
}
dis[s]=0,f=e=1,q[1]=s,inq[s]=true;
spfa();
for(int i=1;i<=n;i++)
printf("%d\n",dis[i]);
return 0;
}
```
❀完结撒花❀