算法作业5

#include
#include
using namespace std;

struct job{  //定义作业结构体 
    int id;  //作业id 
    int time;  //作业运行时间 
};
    
bool compareMethod(job j1,job j2){
    if(j1.time ==j2.time ){  //如果有作业运行时间相同,则按照id递增的顺序进行作业调度 
        return j1.id>number;
     
    job task[number]; 
    cout<<"n 请输入每个作业的各自运行时间:";
    for(int i=0;i>task[i].time;
    } 
    cout<<"n 每个作业的id和各自运行时间显示如下:"< 
所有的作业执行时间之和不会因为调度顺序而改变，因此不同的调度顺序只会导致不同的等待时间。由题可知，等待时间也属于作业的调度时间，因此需要尽量减少所有作业的等待时间，即采用贪心的思想，执行越快的作业优先级越高。总体的等待时间就会越短，因此就先比较执行时间，如果执行时间相同则比较作业的进入顺序，总的来说就是最短作业优先。
 因此该方法可以得到最优解
 
p250.a Prim算法 
树中顶点
余下的顶点
a(-,-)
b(a,5),c(a,7),d(-,∞),e(a,2)
e(a,2)
b(e,3),c(e,4),d(e,5)
b(e,3)
c(e,4),d(e,5)
c(e,4)
d(c,4)
d(c,4)

p255.1.1 Kruskal 
树中边
边的有序列表
bc 1
bc1 de 2 bd3 dc 4 ab 5 ce 6 ad 6
de2
bc1 de 2 bd3 dc 4 ab 5 ce 6 ad 6
bd3
bc1 de 2 bd3 dc 4 ab 5 ce 6 ad 6
ab5
bc1 de 2 bd3 dc 4 ab 5 ce 6 ad 6
2 判断正误 
a.如果e是加权连通图中权重最小的边，它至少是图的一棵最小生成树的边
 正确
 b.如果e是加权连通图中权重最小的边，它必定是图的一棵最小生成树的边
 错误，如果有几条相同的最小权重的边，则有可能不会将其中一条最小边加入最小生成树
 c.如果加权连通图中每条边的权重都是互不相同的，该图必定只有一棵最小生成树
 正确
 d.如果加权连通图中每条边的权重都是互不相同的，该图必定不止有一棵最小生成树
 错误，图中存在环时会有可能只有一棵或几棵最小生成树
 
P259 2.a 
树中顶点
余下的顶点
a(-,0)
b(-,∞),c(-,∞),d(a,7),e(-,∞)
d(a,7)
b(d,2),c(d,5),e(-,∞)
b(d,2)
c(b,4),e(-,∞)
c(b,4)
e(c,6)
e(c,6)

P264 1 
a
 
 
A
B
C
D
_
0.4
0.1
0.2
0.15
0.15
0
100
111
101
110
b
 ABACABAD 0100011101000101
 c
 
100
0
101
110
0
101
0
B
A
D
_
A
D
A