关键路径 p3 清华复试上机题

题目描述

小H为了完成一篇论文，一共要完成n个实验。其中第i个实验需要a[i]的时问去完成。小H可以同时进行若干实验，但存在一些实验，只有当它的若干前置实验完成时，才能开始进行该实验。同时我们认为小H在一个实验的前置实验都完成时，就能马上开始该实验。
为了让小H 尽快完成论文，需要知道在最优的情况下，最后一个完成的实验什么时候完成。
小H还想知道，在保证最后一个实验尽快完成的情况下（即保证上一间的答案不变），他想知道每个实验最晚可以什么时候开始。
设第i个实验最早可能的开始时问为fi，不能响最后一个实验完成时间的最晚开始时间为gi,请证明\(\prod_{i=0}^{n}(g_i-f_i+1)\)除以\(10^9+7\)所得的余数能够保证题目有解。

输入

从标淮输入读入数据。
第一行输入两个整数n，m。
第二行输入n个正整数 a，a[2],…，a[n]，描述完成每个实验所需要的时间。
接下来读入 m 行，每行读入两个整数u，v，表示编号为u的实验是编号为v的实验的前置实验。
对于所有的输入数据，都满足\(1\leqslant n \leqslant 10^5\),\(1\leqslant m \leqslant 5×10^5\),\(1\leqslant a_i\leqslant 10^6\).

输出

输出到标准输出。
第一行输出一个整数，表示完成实验的时间。
第二行输出一个整数表示\(\prod_{i=0}^{n}(g_i-f_i+1)\)除以\(10^9+7\)所得的余数。

样例输入

7 5
11 20 17 10 11 17 17
5 4
6 1
7 3
2 4
2 1

样例输出

34
7840

解题思路

求关键路径的长度，记录每个实验最早开始时间和最晚开始时间。典型关键路径问题。

代码实现

#include

using namespace std;

typedef long long ll;

const int maxn = 1e5 + 7;
const int INF = INT_MAX;
const int MOD = 1e9 + 7;

vector graph[maxn];
int inDegree[maxn];
ll earliest[maxn];
ll latest[maxn];
ll timee[maxn];

ll criticalPath(int n) {
    vector topology;
    queue q;
    for (int i = 1; i <= n; ++i) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }
    ll totalTime = 0;//总耗时
    while (!q.empty()) {
        int u = q.front();
        topology.push_back(u);
        q.pop();
        for (int i = 0; i < graph[u].size(); ++i) {
            int v = graph[u][i];
            inDegree[v]--;
            earliest[v] = max(earliest[v], timee[u] + latest[u]);//取最大值的原因：只有当前结点的所有前驱结点活动全部完成，才能完成本结点
            if (inDegree[v] == 0) {
                q.push(v);
                totalTime = max(totalTime, earliest[v] + timee[v]);//关键路径长度为最大路径长度的路径
            }
        }
    }
    for (int i = topology.size() - 1; i >= 0; --i) {//逆拓扑排序求最迟开始时间
        int u = topology[i];
        if (graph[u].size() == 0) {
            latest[u] = totalTime - timee[u];//出度为0的点，最晚开始时间为关键路径长度减去其耗费时间
        } else {
            latest[u] = INF;//后面要求最小值，初始化为极大值
        }
        for (int j = 0; j < graph[u].size(); ++j) {
            int v = graph[u][j];
            latest[u] = min(latest[u], latest[v] - timee[u]);//非出度为0的点，最晚开始时间为所有其后续节点最晚开始时间减去该节点耗费时间的最小值
        }
    }
    return totalTime;
}

int main() {
    int n, m;
    while (cin >> n >> m) {
        memset(graph, 0, sizeof graph);
        memset(inDegree, 0, sizeof inDegree);
        memset(earliest, 0, sizeof earliest);
        memset(latest, 0, sizeof latest);
        memset(timee, 0, sizeof timee);
        for (int i = 1; i <= n; i++) {
            cin >> timee[i];
        }
        while (m--) {
            int from, to;
            cin >> from >> to;
            graph[from].push_back(to);
            inDegree[to]++;
        }
        ll totalTime = criticalPath(n);
        ll answer = 1;
        for (int i = 1; i <= n; ++i) {
            answer *= latest[i] - earliest[i] + 1;
            answer %= MOD;
        }
        cout << totalTime << endl << answer << endl;
    }
    return 0;
}