江苏冬令营解题报告

1、工程规划问题描述一个工程有不超过 100 个项目，有 SAS，FAS，SAF 四种可能的制约关系，求一种安排方案，使满足给定的制约关系，并且使工程在最短的时间内结束。输出所有工程最早的开始时间。如果不存在可行的方案，输出一个 0。算法分析读完题后觉得似乎和图论中的最短路径有一定的联系，然而条件给得比较抽象，如何构造图轮模型呢？要求的是各工程最早的开始时间，同时题目中的四种制约关系均可以表示为工程开始时间的相互制约关系，以每个工程的最早开始时间为顶点，设项目持续时间分别为tp，tq，按如下规则建立有向图：SAS p q FAS p q SAF p q FAF p q从q 向p 引一条权为 0 的

2、弧 从q 向p 引一条权为-tp 的弧从q 向p 引一条权为tq 的弧从q 向p 引一条权为tq-tp 的弧各条弧指向的方向表示一个不等关系，即spsq+弧上的权值。再虚设一个源点，从源点向每个点引一条权为 0 的弧，开始时，源点的开始时间为 0，求从源点到各点的最长路径，即为该点的最早开始时间。相应地很容易求出工程完成的总时间。即最晚完成的项目的时间。如何判断无解的情况呢？显然，如果图中存在一个圈，圈上的权和是一个正数，就无解。为方便判断，每个点再引一条权为 0 的自反弧。最后一个关键是，图中的权是存在负数的，如何求最长路呢？这里就要巧妙运用FLOYD 的动态规划了，不展开详述。该算法时间复

3、杂度为O（n*n*n），空间复杂度为 O（n*n），是完全可以承受的。n 在 100 以内，程序program t203; constMAXN=101;vard :array1.MAXN,1.MAXNof adj:array1.MAXN,1.MAXNofeger;两个点之间的最长距离;表示两个点只是否可以达到n :eger;项目总数lt :array1.MAXNof byte;每个项目的持续时间procedure init; 打开输入输出文件 vars1,s2:string;beginwrin(Input file name:);readln(s1);wrin(Input output fil

4、ename:);readln(s2); assign(input,s1); reset(input); assign(output,s2);rewrite(output);end;procedure over; 关闭文件 beginclose(input); close(output);end;function readed: varsln,s1,s2:string;codebegin:eger;readln(sln);while sln= do readln(sln); if sln=# thenreaded:=false elsebeginval(sln,n,code); readed:=

5、true;end;end;procedure readdata; vari:eger;p,q:eger;s:string;p0,code:eger;der:string3;beginfillchar(d,sizeof(d),0);距离表初始化fillchar(adj,sizeof(adj),0); 邻接矩阵初始化for i:=1 to n do adji,i:=true; 每个点添加自反弧 fillchar(lt,sizeof(lt),0);for i:=1 to n do readln(lti);读每个项目的消耗时间 readln(s);while s do beginder:=copy(s

6、,1,3);读入命令s:=copy(s,5,length(s)-4);p0:=( ,s);val(copy(s,1,p0-1),p,code);val(copy(s,p0+1,length(s)-p0),q,code); 分解出p 和 q 的序号adjq,p:=true;表示从 q 到 p 的路径已计算if if ififder=SAS der=FAS der=SAFder=FAFthen then thenthendq,p:=0; 添为 0dq,p:=-ltp;权为-tpdq,p:=ltq; 权为 tq dq,p:=ltq-ltp; 权为 tq-tpreadln(s);end;for i:=

7、1 to n do beginadjn+1,i:=true; dn+1,i:=0;end;从源点 n+1 向每个点引一条权为 0 的弧end;procedure main;vari,j,k:eger;finishtime:eger; beginfor k:=1 to n+1 dofor i:=1 to n+1 do for j:=1 to n+1 doif adji,k andadjk,j and(di,k+dk,jdi,j)or(adji,j=false) then beginif i=j then 若存在正圈，则无解 beginwrin(0); exit;end; adji,j:=true;di,j:=di,k+dk,j;更新距离表end;for i:=1 to n dowrin(i, ,dn+1,i);输出各项目的最早开始时间finishtime:=0; for i:=1 to n doif dn+1,i+ltifinishtime then finishtime:=dn+1,i+lti;结束时间为各项目完成时间中的最大值wrin(Finish at:,finishtime);输出工程的结束时间end;begininit;while readed do beginreaddata;m