USACO历年黄金组真题解析 | 2020年2月Timeline

​欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

• 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
• 希望系统学习C++/Python编程的初学者
• 想要提升算法与编程能力的编程爱好者

附上汇总贴：USACO历年黄金组真题解析 | 汇总

【题目来源】

洛谷：[P6145 USACO20FEB] Timeline G - 洛谷

【题目描述】

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

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

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

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

• 第i ii次挤奶不早于第S i S_iSi​天进行，且不晚于第M MM天进行；
• 所有的记忆都得到满足；

【输入】

第一行三个整数N , M , C N,M,CN,M,C。保证1 ≤ N , C ≤ 10 5 1 \leq N,C \leq 10^51≤N,C≤105，2 ≤ M ≤ 10 9 2 \leq M \leq 10^92≤M≤109。

接下来一行包含N NN个整数S 1 , S 2 , … , S n S_1, S_2 , \ldots, S_nS1​,S2​,…,Sn​，保证∀ 1 ≤ i ≤ n \forall 1 \leq i \leq n∀1≤i≤n，都满足1 ≤ S i ≤ M 1 \leq S_i \leq M1≤Si​≤M。

下面C CC行每行三个整数a , b , x a,b,xa,b,x，描述一条记忆。保证a ≠ b a \neq ba=b，且1 ≤ x ≤ M 1 \leq x \leq M1≤x≤M。

【输出】

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

【输入样例】

4 10 3 1 2 3 4 1 2 5 2 4 2 3 4 4

【输出样例】

1 6 3 8

【算法标签】

《洛谷 P6145 Timeline》 #图论# #拓扑排序# #差分约束# #USACO# #2020#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=100005,M=N*2;// 最大顶点数和边数intn,m,c;// n: 顶点数, m: 未使用, c: 有向边数量ints[N];// 每个顶点的权值inth[N],e[M],w[M],ne[M],idx;// 链式前向星存储图intcnt[N],dist[N];// cnt未使用, dist: 最长距离数组boolst[N];// 标记顶点是否在队列中/** * 添加有向边 * @param a 起点 * @param b 终点 * @param c 权重 */voidadd(inta,intb,intc){e[idx]=b;// 边指向的顶点w[idx]=c;// 边的权重ne[idx]=h[a];// 指向原链表头h[a]=idx++;// 更新头指针}/** * SPFA算法求最长路径 * 从超级源点0开始，计算到所有顶点的最长路径 */voidspfa(){// 初始化距离为负无穷memset(dist,-0x3f,sizeof(dist));queue<int>q;// SPFA队列q.push(0);// 超级源点入队st[0]=true;// 标记在队列中dist[0]=0;// 起点距离为0while(!q.empty()){intt=q.front();// 取出队首q.pop();st[t]=false;// 标记不在队列中// 遍历t的所有邻接边for(inti=h[t];i!=-1;i=ne[i]){intj=e[i];// 邻接顶点// 松弛操作：求最长路径if(dist[j]<dist[t]+w[i]){dist[j]=dist[t]+w[i];// 更新最长距离// 如果j不在队列中，入队if(!st[j]){q.push(j);st[j]=true;}}}}}intmain(){// 输入顶点数，m未使用，有向边数量ccin>>n>>m>>c;// 初始化邻接表memset(h,-1,sizeof(h));// 输入每个顶点的权值s[i]for(inti=1;i<=n;i++){cin>>s[i];// 添加超级源点到每个顶点的边// 权重为s[i]，表示从0出发可以直接获得s[i]的权值add(0,i,s[i]);}// 输入c条有向边for(inti=1;i<=c;i++){inta,b,x;cin>>a>>b>>x;add(a,b,x);// 添加有向边a→b，权重x}// 执行SPFA算法求最长路径spfa();// 输出从超级源点到每个顶点的最长路径长度for(inti=1;i<=n;i++){cout<<dist[i]<<endl;}return0;}

【运行结果】

4 10 3 1 2 3 4 1 2 5 2 4 2 3 4 4 1 6 3 8