利用拓扑排序计算工程完成的最短时间

题目描述

有一项大的工程，工程中有许多前后依赖的子任务，每个子任务都规划了完成需要的天数，假设给出用字母表示的事件结点，整个工程的开始事件用A表示，工程结束事件用Z表示，用事件结点有序对表示一个子任务的开始和结束，并给出每个子任务完成需要的天数。请编程求解完成这个工程的最短天数。

输入

第一行是事件结点的个数N（N<26）和子任务数M。 从第二行开始M行，每行是子任务的开始事件和结束事件以及完成该子任务所需天数。

输出

完成该工程所需的最少天数。

样例输入

4 3
A B 6
B Z 2
A Z 5

样例输出

8

Code

#include 
using namespace std;
const int N = 1000;
vector top_seq;
vector v; // 记录节点
int n, m;
int h[N], ne[N], w[N], e[N], idx;
int d[N];
int dist[N][N];

int earliest_time[N];

void add(int a, int b, int c)
{
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++;
    dist[a][b] = c;
}

void top_sort()
{
    queue q;
    earliest_time['A'] = 0;
    for (auto x : v)
    {
        if (d[x] == 0)
            q.push(x);
    }
    while (!q.empty())
    {
        int t = q.front();
        q.pop();
        top_seq.push_back(t);
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            d[j]--;
            earliest_time[j] = max(earliest_time[j], earliest_time[t] + w[i]); // 这里要取最大值, 因为我们需要等所有前驱节点都完成才能完成当前节点
            if (d[j] == 0)
                q.push(j);
        }
    }
}
int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof(h));
    memset(earliest_time, -1, sizeof earliest_time);
    for (int i = 0; i < m; i++)
    {
        char a, b;
        int c;
        cin >> a >> b >> c;
        v.push_back(a);
        v.push_back(b);
        d[b]++; // 入度加1
        add(a, b, c);
    }
    top_sort();

    cout << earliest_time['Z'] << endl;
    return 0;
}

在拓扑排序中计算最短时间时，取最大值的原因是为了确保每个节点的最早开始时间是所有可能的前驱节点中最晚的那个。

1. 依赖关系：在一个有向无环图中，一个节点的最早开始时间取决于其所有前驱节点的完成时间。只有当所有前驱节点都完成时，当前节点才能开始。

2. 最早开始时间：为了确保当前节点的最早开始时间是最优的，我们需要考虑所有可能的前驱节点的最早开始时间加上它们到当前节点的边的权重。

3. 取最大值的原因：

   • 确保依赖关系满足：如果一个节点有多个前驱节点，那么它的最早开始时间应该是所有前驱节点中最晚完成的时间。这是因为只有当所有前驱节点都完成时，当前节点才能开始。
   • 避免提前开始：如果取最小值，可能会导致当前节点在某些前驱节点还未完成时就提前开始，这显然是不合理的。

4. 具体例子：

   • 假设节点 j 有两个前驱节点 t1 和 t2，它们的最早开始时间分别是 earliest_time[t1] 和 earliest_time[t2]，并且它们到 j 的边的权重分别是 w1 和 w2。

   • 那么节点 j 的最早开始时间应该是：

     $$\text{earliest_time}[j] = \max(\text{earliest_time}[t1] + w1, \text{earliest_time}[t2] + w2)$$

   • 这是因为节点 j 必须等待所有前驱节点都完成才能开始。

总结来说，取最大值是为了确保当前节点的最早开始时间是所有可能的前驱节点中最晚的那个，从而保证任务的依赖关系得到满足，并且任务的开始时间是最优的。