总结
做的……
不是令人满意的结果，历时一个月，靠，大梁半个月……
  关键子工程（project.c/cpp/pas）
在大型工程的施工前，我们把整个工程划分为若干个子工程，并把这些子工程编号为1、2、……、N；这样划分之后，子工程之间就会有一些依赖关系，即一些子工程必须在某些子工程完成之后才能施工。由于子工程之间有相互依赖关系，因此有两个任务需要我们去完成：首先，我们需要计算整个工程最少的完成时间；同时，由于一些不可预测的客观因素会使某些子工程延期，因此我们必须知道哪些子工程的延期会影响整个工程的延期，我们把有这种特征的子工程称为关键子工程，因此第二个任务就是出所有的关键子工程，以便集中精力管理好这些子工程，尽量避免这些子工程延期，达到用最快的速度完成整个工程。为了便于编程，现在我们假设：
（1）根据预算，每一个子工程都有一个完成时间。
（2）子工程之间的依赖关系是：部分子工程必须在一些子工程完成之后才开工。
（3）只要满足子工程间的依赖关系，在任何时刻可以有任何多个子工程同时在施工，也既同时施工的子工程个数不受限制。
（4）整个工程的完成是指：所有子工程的完成。
例如，有五个子工程的工程规划表
五个子工程的工程规划表： 序号
完成时间
子工程1
子工程2
子工程3
子工程4
子工程5
子工程1
5
 
0
0
    0
子工程2
4
0
 
0
0
子工程3
12
0
0
 
0
子工程4
7
1
1
0
0
子工程5
2
1
1
1
     
其中，表格中第I+1行J+2列的值如为0表示“子工程I”可以在“子工程J”没完成前施工，为1表示“子工程I”必须在“子工程J”完成后才能施工。上述工程最快完成时间为14天，其中子工程1、3、4、5为关键子工程。
输入数据：
第1行为N，N是子工程的总个数，N≤200。
第2行为N个正整数，分别代表子工程1、2、……、N的完成时间。
第3行到N+2行，每行有N-1个0或1。其中的第I+2行的这些0，1，分别表示“子工程I”与子工程1、2、…、I-1、I+1、…N的依赖关系，（I=1、2、……、N）。每行数据之间均用一个空格分开。
输出数据：
如子工程划分不合理，则输出-1；
如子工程划分合理，则用两行输出：第1行为整个工程最少的完成时间。第2行为按由小到大
顺序输出所有关键子工程的编号。
样例：
输入文件名：project.in
5
5 4 12 7 2
0 0 0 0
0 0 0 0
0 0 0 0
字符串长度大于51 1 0 0
1 1 1 1
输出文件名：project.out
14
1 3 4 5
关键路径。
2.求关键路径的最大的代价:
  1)将网拓扑排序
  2)以拓扑序列划分阶段
  3)用动态规划求解关键路径
3.求关键路径的节点:
  若结点的排列已经过拓扑排序，即序号前面的结点会影响序号后面结点的活动，如下图。
可使用如下算法:
 (1)求活动最早可以开始的时间
      eet[1]:=0;eet[k]:=max(eet[j]+r[j,k])
 (2)求活动最迟应该开始的时间
      et[n]:=eet[n];et[k]:=min(et[j]-r[k,j]);
 (3)  关键路径通过点J，具有如下的性质：eet[j]=et[j]
  机器分配（machine.c/cpp/pas）
某总公司拥有高效生产设备M台，准备分给下属的N个分公司。各分公司若获得这些设备，可以为总公司提供一定的盈利。问：如何分配这M台设备才能使国家得到的盈利最大？求出最大盈利值。
分配原则：每个公司有权获得任意数目的设备，但总台数不得超过总设备数M。其中M<=100，N<=100。
输入数据：
第一行为两个整数M，N。接下来是一个N×M的矩阵，其中矩阵的第i行的第j列的数Aij表明第i个公司分配j台机器的盈利。所有数据之间用一个空格分隔。
输出数据：
只有一个数据，为总公司分配这M台设备所获得的最大盈利。
样例
输入文件名：machine.in
3 2
1 2 3
2 3 4
输出文件名：machine.out 
4
状态的分析: f[I，J] 表示前I个公司分得J个机器所得的最大的价值，

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。