校车安排问题c语言源程序.docx
- 文档编号:10508570
- 上传时间:2023-05-26
- 格式:DOCX
- 页数:79
- 大小:55.83KB
校车安排问题c语言源程序.docx
《校车安排问题c语言源程序.docx》由会员分享,可在线阅读,更多相关《校车安排问题c语言源程序.docx(79页珍藏版)》请在冰点文库上搜索。
校车安排问题c语言源程序
B题校车安排问题
许多学校都建有新校区,常常需要将老校区的教师和工作人员用校车送到新校区。
由于每天到新校区的教师和工作人员很多,往往需要安排许多车辆。
如何有效的安排车辆及让教师和工作人员尽量满意是个十分重要的问题。
现有如下问题请你设计解决。
假设老校区的教师和工作人员分布在50个区,各区的距离见表1。
各区人员分布见表2。
问题1:
如要建立
个乘车点,为使各区人员到最近乘车点的距离最小,该将校车乘车点应建立在哪
个点。
建立一般模型,并给出
时的结果。
问题2:
若考虑每个区的乘车人数,为使教师和工作人员满意度最大,该将校车乘车点应建立在哪
个点。
建立一般模型,并给出
时的结果。
问题3若建立3个乘车点,为使教师和工作人员尽量满意,至少需要安排多少辆车?
给出每个乘车点的位置和车辆数。
设每辆车最多载客47人。
问题4;关于校车安排问题,你还有什么好的建议和考虑。
可以提高乘车人员的满意度,又可节省运行成本。
表1各区距离表
区域号
区域号
距离(m)
1
2
400
1
3
450
2
4
300
2
21
230
2
47
140
3
4
600
4
5
210
4
19
310
5
6
230
5
7
200
6
7
320
6
8
340
7
8
170
7
18
160
8
9
200
8
15
285
9
10
180
10
11
150
10
15
160
11
12
140
11
14
130
12
13
200
13
34
400
14
15
190
14
26
190
15
16
170
15
17
250
16
17
140
16
18
130
17
27
240
18
19
204
18
25
180
19
20
140
19
24
175
20
21
180
20
24
190
21
22
300
21
23
270
21
47
350
22
44
160
22
45
270
22
48
180
23
24
240
23
29
210
23
30
290
23
44
150
24
25
170
24
28
130
26
27
140
26
34
320
27
28
190
28
29
260
29
31
190
30
31
240
30
42
130
30
43
210
31
32
230
31
36
260
31
50
210
32
33
190
32
35
140
32
36
240
33
34
210
35
37
160
36
39
180
36
40
190
37
38
135
38
39
130
39
41
310
40
41
140
40
50
190
42
50
200
43
44
260
43
45
210
45
46
240
46
48
280
48
49
200
表2各区人员分布
区域
人数
区域
人数
1
65
26
16
2
67
27
94
3
42
28
18
4
34
29
29
5
38
30
75
6
29
31
10
7
17
32
86
8
64
33
70
9
39
34
56
10
20
35
65
11
61
36
26
12
47
37
80
13
66
38
90
14
21
39
47
15
70
40
40
16
85
41
57
17
12
42
40
18
35
43
69
19
48
44
67
20
54
45
20
21
49
46
18
22
12
47
68
23
54
48
72
24
46
49
76
25
76
50
62
以上数据仅供参考,不一定完全符合实际。
校车安排问题c语言源程序
原题:
1、
2、
3、
4、
5、
1、第一题(2个车站):
/***************************************
*此程序功能是在50个小区中如要建立2个乘
*车点,为使各区人员到最近乘车点的距离最
*小,该将校车乘车点应建立在哪2个点
***************************************/
#include
#include
#defineMAX_VERTEX_NUM51//矩阵大小51*51,a[0][i]与a[i][0]不用
#defineTRUE1
#defineFALSE0
#defineINFINITY32767//用整型最大值代替∞
typedefintVERTYPE;
///////////////////////////////////////////////////////
//mgraph数据结构
typedefstruct
{
VERTYPEvexs[MAX_VERTEX_NUM];//顶点向量
intarcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵//点与点间距离,即弧线
intvexnum,arcnum;//图的当前顶点数和弧数
}mgraph,*MGraph;
typedefintPathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//两点间是否可达
typedefintShortPathTable[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//点到点的最短长度
///////////////////////////////////////////////////////
//初始化图
voidinit_mgraph(MGraph&g)
{
g=(MGraph)malloc(sizeof(mgraph));
g->vexnum=50;//初始顶点数位50
g->arcnum=0;//初始弧数为0
for(inti=1;i<=g->vexnum;i++)
{
g->vexs[i]=i;
}
for(i=1;i<=g->vexnum;i++)
{
for(intj=1;j<=g->vexnum;j++)
{
g->arcs[i][j]=(i==j?
0:
INFINITY);
}
}
//////////////////////////////////////////
//无向图由两部分构成,即A--->B的有向图和//
//B--->A的有向图//
//////////////////////////////////////////
/*下面首先构建A---->B的有向图*/
g->arcs[1][2]=400;
g->arcs[1][3]=450;
g->arcs[2][4]=300;
g->arcs[2][21]=230;
g->arcs[2][47]=140;
g->arcs[3][4]=600;
g->arcs[4][5]=210;
g->arcs[4][19]=310;
g->arcs[5][6]=230;
g->arcs[5][7]=200;
g->arcs[6][7]=320;
g->arcs[6][8]=340;
g->arcs[7][8]=170;
g->arcs[7][18]=160;
g->arcs[8][9]=200;
g->arcs[8][15]=285;
g->arcs[9][10]=180;
g->arcs[10][11]=150;
g->arcs[10][15]=160;
g->arcs[11][12]=140;
g->arcs[11][14]=130;
g->arcs[12][13]=200;
g->arcs[13][34]=400;
g->arcs[14][15]=190;
g->arcs[14][26]=190;
g->arcs[15][16]=170;
g->arcs[15][17]=250;
g->arcs[16][17]=140;
g->arcs[16][18]=130;
g->arcs[17][27]=240;
g->arcs[18][19]=204;
g->arcs[18][25]=180;
g->arcs[19][20]=140;
g->arcs[19][24]=175;
g->arcs[20][21]=180;
g->arcs[20][24]=190;
g->arcs[21][22]=300;
g->arcs[21][23]=270;
g->arcs[21][47]=350;
g->arcs[22][44]=160;
g->arcs[22][45]=270;
g->arcs[22][48]=180;
g->arcs[23][24]=240;
g->arcs[23][29]=210;
g->arcs[23][30]=290;
g->arcs[23][44]=150;
g->arcs[24][25]=170;
g->arcs[24][28]=130;
g->arcs[26][27]=140;
g->arcs[26][34]=320;
g->arcs[27][28]=190;
g->arcs[28][29]=260;
g->arcs[29][31]=190;
g->arcs[30][31]=240;
g->arcs[30][42]=130;
g->arcs[30][43]=210;
g->arcs[31][32]=230;
g->arcs[31][36]=260;
g->arcs[31][50]=210;
g->arcs[32][33]=190;
g->arcs[32][35]=140;
g->arcs[32][36]=240;
g->arcs[33][34]=210;
g->arcs[35][37]=160;
g->arcs[36][39]=180;
g->arcs[36][40]=190;
g->arcs[37][38]=135;
g->arcs[38][39]=130;
g->arcs[39][41]=310;
g->arcs[40][41]=140;
g->arcs[40][50]=190;
g->arcs[42][50]=200;
g->arcs[43][44]=260;
g->arcs[43][45]=210;
g->arcs[45][46]=240;
g->arcs[46][48]=280;
g->arcs[48][49]=200;
/*构建B---->A的有向图*/
g->arcs[2][1]=400;
g->arcs[3][1]=450;
g->arcs[4][2]=300;
g->arcs[21][2]=230;
g->arcs[47][2]=140;
g->arcs[4][3]=600;
g->arcs[5][4]=210;
g->arcs[19][4]=310;
g->arcs[6][5]=230;
g->arcs[7][5]=200;
g->arcs[7][6]=320;
g->arcs[8][6]=340;
g->arcs[8][7]=170;
g->arcs[18][7]=160;
g->arcs[9][8]=200;
g->arcs[15][8]=285;
g->arcs[10][9]=180;
g->arcs[11][10]=150;
g->arcs[15][10]=160;
g->arcs[12][11]=140;
g->arcs[14][11]=130;
g->arcs[13][12]=200;
g->arcs[34][13]=400;
g->arcs[15][14]=190;
g->arcs[26][14]=190;
g->arcs[16][15]=170;
g->arcs[17][15]=250;
g->arcs[17][16]=140;
g->arcs[18][16]=130;
g->arcs[27][17]=240;
g->arcs[19][18]=204;
g->arcs[25][18]=180;
g->arcs[20][19]=140;
g->arcs[24][19]=175;
g->arcs[21][20]=180;
g->arcs[24][20]=190;
g->arcs[22][21]=300;
g->arcs[23][21]=270;
g->arcs[47][21]=350;
g->arcs[44][22]=160;
g->arcs[45][22]=270;
g->arcs[48][22]=180;
g->arcs[24][23]=240;
g->arcs[29][23]=210;
g->arcs[30][23]=290;
g->arcs[44][23]=150;
g->arcs[25][24]=170;
g->arcs[28][24]=130;
g->arcs[27][26]=140;
g->arcs[34][26]=320;
g->arcs[28][27]=190;
g->arcs[29][28]=260;
g->arcs[31][29]=190;
g->arcs[31][30]=240;
g->arcs[42][30]=130;
g->arcs[43][30]=210;
g->arcs[32][31]=230;
g->arcs[36][31]=260;
g->arcs[50][31]=210;
g->arcs[33][32]=190;
g->arcs[35][32]=140;
g->arcs[36][32]=240;
g->arcs[34][33]=210;
g->arcs[37][35]=160;
g->arcs[39][36]=180;
g->arcs[40][36]=190;
g->arcs[38][37]=135;
g->arcs[39][38]=130;
g->arcs[41][39]=310;
g->arcs[41][40]=140;
g->arcs[50][40]=190;
g->arcs[50][42]=200;
g->arcs[44][43]=260;
g->arcs[45][43]=210;
g->arcs[46][45]=240;
g->arcs[48][46]=280;
g->arcs[49][48]=200;
}
///////////////////////////////////////////////////////
//Dijkstra算法
voidShortestPath_DIJ(MGraphg,intv0,intP[][51],intD[][51])//tag
{//用Dijkstra算法求有向网G的v0顶点到其余顶点v的最短路径P[v]及带权长度D[v]。
//若P[v][w]为TRUE,则w是从v0到v当前求得最短路径上的顶点。
确定两点是否可连接
//final[v]为TRUE当且仅当v∈S,即已经求得从v0到v的最短路径。
intv,w,i,j,min;
intfinal[MAX_VERTEX_NUM];//对应点是否在S中
for(v=1;v<=g->vexnum;++v)
{
final[v]=FALSE;
D[v0][v]=g->arcs[v0][v];
if(D[v0][v] { P[v0][v]=TRUE;//v0是v0直接到达v的路径的始点 } else { P[v0][v]=FALSE; } } final[v0]=TRUE;//初始化,v0顶点属于S集 //开始主循环,每次求得v0到某个v顶点的最短路径,并加入v到S集 for(i=1;i { min=INFINITY;//当前所知离v0顶点的最近距离 for(w=1;w<=g->vexnum;w++) { if(! final[w]&&D[v0][w] { v=w; min=D[v0][w];//w顶点离v0顶点更近 } } final[v]=TRUE;//离v0顶点最近的v加入S集 for(w=1;w<=g->vexnum;w++) {//更新当前最短路径及距离 if(! final[w]&&(min+g->arcs[v][w] {//修改D[w]和P[w],w∈V-S D[v0][w]=min+g->arcs[v][w];//修改当前路径长度 for(j=1;j<=g->vexnum;++j) { P[w][j]=P[v][j];//将经过v点的路径复制过来 } P[w][w]=TRUE;//最后的重点为TURE } } } } /////////////////////////////////////////////////////// //main主函数 voidmain() { inti,j,k,l; intnum=0;//num用于换行 MGraphG; init_mgraph(G);//初始化图 PathMatrixP;//p[0]不用 ShortPathTableD;//求某点到其余各点的最短路径,D[0]不用 for(i=1;i<=G->vexnum;++i)//求50个点到其余个点的最短距离 { ShortestPath_DIJ(G,i,P,D);//tag } /*输出最短路径的位置*/ /*for(i=1;i<=G->vexnum;++i) { printf("顶点%d的最短路径数组p[i][j]如下: \n",i); for(j=1;j<=G->vexnum;++j) { for(k=1;k<=G->vexnum;++k) { printf("%d",P[i][j][k]); ++num; if(num%50==0) printf("\n"); if(j*k%2500==0) printf("\n\n"); } } }*/ /* printf("源点到各顶点的最短路径长度如下: \n"); for(i=1;i<=G->vexnum;++i) { printf("源点顶点距离\n"); for(intj=1;j<=G->vexnum;++j) printf("%d%d%d\n",G->vexs[v[i]],G->vexs[j],D[i][j]); printf("\n"); if(i<50) printf("*****************************"); printf("\n");; }*/ printf("各源点到各顶点的最短路径长度矩阵如下: \n"); for(i=1;i<=G->vexnum;++i) { printf("%d",i); for(j=1;j<=G->vexnum;++j) printf("%-4d",D[i][j]); printf("\n"); } intmin; intsum[51][51]; for(i=1;i<=G->vexnum-1;++i) for(j=i+1;j<=G->vexnum;++j) sum[i][j]=0; for(i=1;i<=G->vexnum-1;++i) for(j=i+1;j<=G->vexnum;++j) for(l=1;l<=G->vexnum;++l) { min=((D[i][l] D[i][l]: D[j][l]); sum[i][j]+=min; } intMIN=sum[1][2]; for(i=1;i<=G->vexnum-1;++i) for(j=i+1;j<=G->vexnum;++j) if(MIN>sum[i][j]) MIN=sum[i][j]; printf("\n最短距
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 校车 安排 问题 语言 源程序