四个最大流计算问题的计算

从1到14的最大流问题，最好能解释一下计算过程谢谢

从1到8的最大流问题

确定节点1到节点7的最短距离

有用希望点一下采纳，谢谢
以最后一个图为例进行说明：
一、首先按权重从小到大的顺序，对边进行排列编号：

二、从图中所有的边中选择可以构成最小生成树的边(也就是不会形成环)，知道最小生成树上包含了n-1条边(也就是6条)
1.选择边2-3，无环，添加

2.选择边3-6，无环，添加

3.选择边1-2，无环，添加

4.选择边5-7，无环，添加

5.选择边3-4，无环，添加

6.选择边4-6，有环，不添加
选择边1-3，有环，不添加
选择边6-7，无环，添加

边数已经达到了n-1
从图中可以看出，
节点1-7的距离为4+3+3+7=17

可以借鉴下

//capacity：容量
//flow：流量
//parent：记录在一条增广路中每个节点的前一个节点
//alpha：记录在增广路中当每个节点所能调整的流量的最大值

int EK(int m)
{
    //初始化操作
    int result = 0;
    for (int i = 1; i <= m; i++)    parent[i] = alpha[i] = 0;
    queue<int> vertexQueue;
    while (true)
    {
        memset(alpha, 0, sizeof(alpha));
        alpha[1] = INF;
        vertexQueue.push(1);
        //BFS过程
        while (!vertexQueue.empty())
        {
            int vtop = vertexQueue.front();
            vertexQueue.pop();
            for (int i = 1 ;  i <= m ; i ++ )
            {
                //如果目标节点还未在增广路中出现并且可以调整流量
                if (!alpha[i] && flow[vtop][i] < capacity[vtop][i])
                {
                    parent[i] = vtop;
                    alpha[i] = min(capacity[vtop][i] - flow[vtop][i], alpha[vtop]);
                    vertexQueue.push(i);
                }
            }
        }
        //汇点可调整流量为0，说明没有增广路了，算法结束
        if (alpha[m] == 0)
        {
            return result;
        }
        //汇点可调整流量不为0，那么找到了增广路，增广路上所有节点做流量调整
        for (int i = m; i != 1; i = parent[i])
        {
            flow[parent[i]][i] += alpha[m];//前向弧流量增加
            flow[i][parent[i]] -= alpha[m];//后向弧流量减少
        }
        //由于一开始流量都为0，调整多少能量就代表整个可行流的流量增加了多少
        result += alpha[m];
    }
}

EK算法
最简单的算法莫过于暴力搜索，而EK算法正是如此。
在每次搜索增广路的时候，都采取BFS的策略，将所有的从源点到汇点的路径都找出来，那么如果有增广路，就一定可以将它找出来。因此采用BFS策略首先是正确的，来看一下它的代码实现：

//capacity：容量
//flow：流量
//parent：记录在一条增广路中每个节点的前一个节点
//alpha：记录在增广路中当每个节点所能调整的流量的最大值

int EK(int m)
{
    //初始化操作
    int result = 0;
    for (int i = 1; i <= m; i++)    parent[i] = alpha[i] = 0;
    queue<int> vertexQueue;
    while (true)
    {
        memset(alpha, 0, sizeof(alpha));
        alpha[1] = INF;
        vertexQueue.push(1);
        //BFS过程
        while (!vertexQueue.empty())
        {
            int vtop = vertexQueue.front();
            vertexQueue.pop();
            for (int i = 1 ;  i <= m ; i ++ )
            {
                //如果目标节点还未在增广路中出现并且可以调整流量
                if (!alpha[i] && flow[vtop][i] < capacity[vtop][i])
                {
                    parent[i] = vtop;
                    alpha[i] = min(capacity[vtop][i] - flow[vtop][i], alpha[vtop]);
                    vertexQueue.push(i);
                }
            }
        }
        //汇点可调整流量为0，说明没有增广路了，算法结束
        if (alpha[m] == 0)
        {
            return result;
        }
        //汇点可调整流量不为0，那么找到了增广路，增广路上所有节点做流量调整
        for (int i = m; i != 1; i = parent[i])
        {
            flow[parent[i]][i] += alpha[m];//前向弧流量增加
            flow[i][parent[i]] -= alpha[m];//后向弧流量减少
        }
        //由于一开始流量都为0，调整多少能量就代表整个可行流的流量增加了多少
        result += alpha[m];
    }
}

从1到14的最大流问题：

a. 对于网络拓扑是一个完全图的情况，最大流量等于容量最小的边。因此，从源点1到终点14的最大流量为3。

b. 对于单向边权的图，可以通过消除反向边、构建残量图、使用增广路径算法来计算最大流量。这个问题的解法可以使用Edmonds-Karp算法。首先构建残量图，然后通过BFS算法找到图中的最短增广路径，即从源点1到终点14的最小容量路径，将这个路径上的流量全部增加，再构建新的残量图，不停地重复上述步骤，直到没有增广路径为止。最后可以得到从源点1到终点14的最大流量为10。

c. 对于含有双向边的图，需要将双向边替换为两条有向边，并将它们的边权分别取为原边权的一半。对于这个问题，可以得到从源点1到终点14的最大流量为10.5。

从1到8的最大流问题：

a. 对于网络拓扑是一个完全图的情况，最大流量等于容量最小的边。因此，从源点1到终点8的最大流量为4。

b. 对于单向边权的图，可以使用Ford-Fulkerson算法来计算最大流量。首先找到一条从源点1到终点8的增广路径，即一条路径上的各个边的流量之和等于路径上的最小边权。然后将这条路径上的流量全部增加，生成新的残量图，并找到下一条增广路径，直到没有增广路径为止。最后可以得到从源点1到终点8的最大流量为8。

c. 对于含有双向边的图，需要将双向边替换为两条有向边，并将它们的边权分别取为原边权的一半。对于这个问题，可以得到从源点1到终点8的最大流量为5.5。

确定节点1到节点7的最短距离：

这个问题可以使用Dijkstra算法来求解。首先将所有节点标记为未访问状态，将开始节点1标记为已访问。然后依次访问与已访问节点相连的所有未访问节点，并将它们到开始节点1的距离值更新为当前路径长度加上该节点的权值。之后从未访问节点中选择距离最短的节点作为下一个访问节点，将该节点标记为已访问，然后再依次访问与该节点相连的所有未访问节点，更新它们到开始节点1的距离值。重复上述步骤，直到找到目标节点7为止。最后可以得到从节点1到节点7的最短距离为11。

这个问题的回答你可以参考下: https://ask.csdn.net/questions/7440574
这篇博客你也可以参考下：二叉树中权值最大的叶节点到权值最小的叶节点的距离
除此之外, 这篇博客: 7-2 然后是几点 (15 分)有时候人们用四位数字表示一个时间，比如 1106 表示 11 点零 6 分。现在，你的程序要根据起始时间和流逝的时间计算出终止时间。读入两个数字，第一个数字以这样中的 输出样例： 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:

结尾无空行

代码：


#include<stdio.h>

int main()
{
    int time,pa;
    scanf("%d %d",&time,&pa);
    int i = 0,flag = 0;
    int  mtim = time / 100;  //  小时数
    int  ntim = time % 100;  //  分钟数
    flag = ntim + pa;
    if (flag >= 0 )
    {
         mtim  += flag/60;
         
         flag %= 60;
    }
 if (flag < 0 )
    {
        flag *= -1;
        mtim  -= flag/60;
        flag %= 60;
        if (flag % 60 > 0)
        {
            mtim--;
            flag = 60 -flag;
        }
         

    }
    if (flag > 9)
    {
        printf("%d%d",mtim,flag);
    }else
    {
        printf("%d0%d",mtim,flag);  // 分钟数小于10，在前面加上0
    }
    return 0;
}

您还可以看一下 Laura Dong老师的备考：亚马逊云科技认证解决方案架构师 – 助理级课程中的备考解决方案架构师 - 模块 1 - 第 13 节 - 样题 7 (2)小节, 巩固相关知识点

图已经给出了，自己计算不就出来了么~