题目描述题目要求为项目中的各个部分安排开始时间使得整个项目完成时间最短。每个部分需要连续若干天完成。约束条件有四种FAS\texttt{FAS}FAS第二部分必须在第一部分开始之后完成。FAF\texttt{FAF}FAF第二部分必须在第一部分完成之后完成。SAF\texttt{SAF}SAF第二部分必须在第一部分完成之后开始。SAS\texttt{SAS}SAS第二部分必须在第一部分开始之后开始。假设有足够的人力可以并行执行任意数量的部分。目标是找到每个部分的最早开始时间令第一个部分的开始时间为000若不存在可行解则输出impossible。输入格式输入包含多个项目每个项目以空行分隔。每个项目的第一行为部分数量nnn。接下来nnn行每行一个整数表示每个部分所需的天数。然后若干行每行一个约束格式为类型 部分1 部分2以#结束。输入以文件结束符EOF\texttt{EOF}EOF终止。输出格式对于每个项目输出Case X:然后每行输出部分编号 开始时间按部分编号顺序。若无解输出impossible。每个项目的输出后跟一个空行。样例输入3 2 3 4 SAF 1 2 FAF 2 3 # 3 1 1 1 SAF 1 2 SAF 2 3 SAF 3 1 #输出Case 1: 1 0 2 2 3 1 Case 2: impossible题目分析本题的核心是建立差分约束系统并求解最短路径。变量定义设tit_iti​为第iii个部分的开始时间did_idi​为第iii个部分所需的天数则完成时间为tidit_i d_iti​di​。约束转化FAS ij\texttt{FAS } i jFASijjjj在iii开始后完成⇒tjdj≥ti⇒tj≥ti−dj\Rightarrow t_j d_j \ge t_i \Rightarrow t_j \ge t_i - d_j⇒tj​dj​≥ti​⇒tj​≥ti​−dj​FAF ij\texttt{FAF } i jFAFijjjj在iii完成后完成⇒tjdj≥tidi⇒tj≥tidi−dj\Rightarrow t_j d_j \ge t_i d_i \Rightarrow t_j \ge t_i d_i - d_j⇒tj​dj​≥ti​di​⇒tj​≥ti​di​−dj​SAF ij\texttt{SAF } i jSAFijjjj在iii完成后开始⇒tj≥tidi\Rightarrow t_j \ge t_i d_i⇒tj​≥ti​di​SAS ij\texttt{SAS } i jSASijjjj在iii开始后开始⇒tj≥ti\Rightarrow t_j \ge t_i⇒tj​≥ti​这些不等式均可写成tv≥tuwt_v \ge t_u wtv​≥tu​w的形式即差分约束中的tu≤tv−wt_u \le t_v - wtu​≤tv​−w。为求解最短路径可转化为tv≤tu(−w)t_v \le t_u (-w)tv​≤tu​(−w)即添加边u→vu \to vu→v权值为−w-w−w。求解添加一个超级源点000与所有节点相连权值为−di-d_i−di​确保ti≥0t_i \ge 0ti​≥0。使用Bellman-Ford\texttt{Bellman-Ford}Bellman-Ford算法判断是否有负环。若无负环则dist[i]dist[i]dist[i]即为tit_iti​的最小可能值。通过减去最小值使第一个部分的开始时间为000。复杂度分析节点数n1≤101n1 \le 101n1≤101边数O(nm)O(n m)O(nm)Bellman-Ford\texttt{Bellman-Ford}Bellman-Ford复杂度O((nm)n)O((nm)n)O((nm)n)可接受。代码实现// Schedule Problem// UVa ID: 522// Verdict: Accepted// Submission Date: 2017-04-28// UVa Run Time: 0.170s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structedge{intu,v,weight;};edge edges[20480];intnedges,days[10240],n,part1,part2,cases0;intdist[10240];string constrain;voidaddEdge(intu,intv,intweight){edges[nedges].uu,edges[nedges].vv,edges[nedges].weightweight;nedges;}intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);while(cinn){coutCase cases:\n;for(inti1;in;i)cindays[i];nedges0;while(cinconstrain,constrain!#){cinpart1part2;if(constrainFAS)addEdge(part2,part1,days[part2]);elseif(constrainFAF)addEdge(part2,part1,days[part2]-days[part1]);elseif(constrainSAF)addEdge(part2,part1,-days[part1]);elseaddEdge(part2,part1,0);}n1;for(inti1;in;i)addEdge(0,i,-days[i]);dist[0]0;for(inti1;in;i)dist[i](130);intiterations0,updated0;do{updated0;for(inti0;inedges;i){intweightdist[edges[i].u]edges[i].weight;if(dist[edges[i].v]weight)updated,dist[edges[i].v]weight;}}while(updatediterationsn);if(updated)coutimpossible\n\n;else{intminDaysdist[1];for(inti2;in;i)minDaysmin(minDays,dist[i]);for(inti1;in;i)couti (dist[i]-minDays)\n;cout\n;}}return0;}