本章开始讲一些计算题了，主要是刷题，每年都会考，原来是在这里啊，之前考高项的时候也有类似的题型，我还好奇这些题出自哪里，原来是系分的这个章节，其实也都是一些算法题，开发出身的应该是似曾相识，估计刷力扣的时候应该会遇到过！其实就是用数学去解决现实中遇到的实际问题了，把实际问题抽象成数学模型，对应现在很火的算法，当然咱们系分要比这个简单，只要掌握解题思路就可以，毕竟上午时间很充足。

1.最小生成树

1.开发商需要在某小区9栋楼房之间敷设自来水管道，使各楼都能连通，又能使总成本最低。经勘察，各楼房之间敷设管道的路径和成本（单位：千元）如下图所示：

A.13 B.14 C.15 D.16

解析：一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。 [1] 最小生成树可以用kruskal（克鲁斯卡尔）算法或prim（普里姆）算法求出。

举例：我们要在n个城市中建立一个通信网络，则连通这n个城市需要布置n-1一条通信线路，这个时候我们需要考虑如何在成本最低的情况下建立这个通信网。

上边是百度搜的，最小生成树概念。

思路：n个节点联通，最少需要n-1个边即可，不能产生环路。

看灵魂画师，一步步画，从成本最低的1开始画，直到没有环路为止

答案选A

2.己知八口海上油井（编号从1#到8#)相互之间的距离（单位：海里）如下表所示，其中1#油井离海岸最近为5海里。现从海岸开始铺设输油管道，经1#油井将这些油井都连接起来，管道的总长度至少为（）海里（为便于计量和维修，管道只能在油井处分叉）

A.5 B.9 C.10 D.11

解析：8个油井7条边，给表格不给图

最小生成树，两种类型的考法，1.给图，2.不给图，给表格

答案C，注意离海岸还有5公里要加上！

2.最短路径

1.下表记录了六个结点A、B、C、D、E、F之间的路径方向和距离。从A到F的最短距离是（）。

A、38 B、40 C、44 D、46

解析：最短路径应该也会出图形，不单单上边的表格，就是穷举了，最简单的方式，没那么多复杂，就是计算比较多！

A-F最短路径，依次求A-F最短路径

A-B：11

A-C：分两个路径1.A-B-C=11+13=26，2.A-C=16

A-D：分A-B-C-D，A-B-D，A-C-D，A-D四个路径，

A-B-C-D=11+13+14=38，A-B-D=11+16=27，A-C-D=16+14=30，A-D=24

A-E：分A-B-C-D-E，A-B-E，A-B-C-E，A-C-D-E，A-C-E，A-D-E，A-E七种路径，

A-B-C-D-E=38+14=52，A-B-E=11+21=32，A-B-C-E=11+13+17=41，A-C-D-E=30+14=44，A-C-E=16+17=33，A-D-E=24+14=38，A-E=36。

A-F：分A-F，

A-B-F，A-B-C-F，A-B-D-F，A-B-E-F，

A-B-C-D-F，A-B-C-E-F，A-B-C-D-E-F，

A-C-F，A-C-D-F，A-C-E-F，

A-C-D-F，A-C-D-E-F，

A-D-F，A-D-E-F，

A-E-F，16中情况：

A-F=54，A-B-F=11+29=40，A-B-C-F=26+22=48，A-B-D-F=27+17=44，A-B-E-F=32+15=47，

A-B-C-D-F=38+17=55，A-B-C-E-F=41+15=56，A-B-C-D-E-F=52+15=67，

A-C-F=16+22=38，A-C-D-F=30+17=47，.............算到这里可以不用算了，答案最低就是38了，选A

思路很清晰，简单有效，就是有点耗时。

3.网络与最大流量

1.下图标出了某地区的运输网，各节点之间的运输能力如下表所示。那么，从节点①到节点⑥的最大运输能力（流量）可以达到多少万吨／小时？

解析：短板优先（比如上图1-2-5-6这个路径为例，最大的运输量取决于最短板1-2的运输量6万吨，多了也运不过去了），实时更新（还是以1-2-5-6路径举例，1-2的6万吨运过去之后，2-5运力7-6=1，只剩下1万吨了，1-2路径就变成0了，理解理解每小时最多的流量），每一次运输的过程都要加起来！

思路就三点：1.短板优先，2.实时更新，3.每次运输都相加，最终得到最大运输量！

路径有很多条，上图只是一种情况，但是所有路径的最终运力结果都是一样的！

2.X、Y、Z是某企业的三个分厂，每个分厂每天需要同一种原料20吨，下图给出了邻近供应厂A、B、C的供应运输路线图，每一段路线上标明了每天最多能运输这种原料的吨数。根据该图可以算出，从A、B、C三厂每天最多能给该企业运来这种原料共（）吨。

A.45 B.50 C.55 D.60

解析：也是网络与最大流量的题，区别与第一题，起点终点不唯一，多个起点多个终点！

大家看图领会做题思路吧！我只是让大家明白思路，完全不用画这么麻烦的图，主要是帮助大家理解。

答案选C

4.线性规划

不止考计算，还考理论，如下：

在一组约束条件下来寻找目标函数的极值（极大值和极小值）问题。

线性规划问题的数学模型通常由线性目标函数、线性约束条件、变量非负条件组成（实际问题中的变量一般都是非负的）。

线性规划问题就是面向实际应用，求解一组非负变量，使其满足给定的一组线性约束条件，并使某个线性目标函数达到极值。满足这些约束条件的非负变量组的集合称为可行解域。

可行解域中使目标函数达到极值的解称为最优解。

线性规划问题的最优解要么是0个（没有），要么是唯一的（1个），要么有无穷个（只要有2个，就会有无穷个）。

在实际应用中，可以直接求约束条件方程组的解，即是交叉点，将这些解代入到目标函数中判断是否极值即可。

1.某企业需要采用甲、乙、丙三种原材料生产I、II两种产品。生产两种产品所需原材料数量、单位产品可获得利润以及企业现有原材料数如下表所示，则公司可以获得的最大利润是（ )万元。取得最大利润时，原材料（ )尚有剩余。

A.21 B.34 C.39 D.48

A.甲 B.乙 C.丙 D.乙和丙

解析：先读懂图的意思吧！然后就是假设未知数，生产I为X，II为Y，就是求9X+12Y的最大值，也就是利润。

我简单解释下：x+y<=4，4x+3y<=12，x+3y<=6这三个式子怎么的出来的，我明明假设的生产I产品x吨，生产II产品Y吨。

每生产1吨I产品，需要1吨甲，按照这个比例，假设x吨I，A吨甲，则A=X

每生产1吨II产品，需要1吨甲，按照这个比例，假设y吨II，B吨甲，则B=Y

A+B<=4（甲的现有原料不能超过4吨），所以x+y<=4！

同理：

每生产1吨I产品，需要4吨乙，按照这个比例，假设x吨I，C吨乙，则1/4=x/C，C=4X,

每生产1吨II产品，需要3吨乙，按照这个比例，假设y吨II，D吨乙，则1/3=y/D，D=3y

C+D<=12（乙的现有原料不能超过12吨），所以4x+3y<=12!

每生产1吨I产品，需要1吨丙，按照这个比例，假设x吨I，E吨丙，则E=X，E=x,

每生产1吨II产品，需要3吨丙，按照这个比例，假设y吨II，F吨丙，则，1/3=y/F，F=3y，

E+F<=6（丙的现有原料不能超过6吨），x+3y<=6!

感谢大伙点赞+关注的支持，是我持续学习更新的动力，关注公众号：Coding-9527，跟大伙一起学习，成长，进步！