晴神の模拟 | 多源点、汇点的AOE关键路径

第一次写关键路径的题，交上去直接AC爽爆！！！然而现在简书发不出去，偷偷爽一下吧😁

1020 | 万妖瞬击

思路

多源点、多汇点，求关键路径。

• 关键路径基本思路见拓扑排序（删边/DFS）➕AOE网关键路径

• 别忘了初始化early、late数组

  • early是最小值中取最大，初始化为-1。
  • late是最大值中取最小，初始化为INF。

• 在输入边的时候，统计出入度，出 = 0的为汇点，入= 0的为源点。

• 拓扑排序，queue存拓扑序，stack存逆拓扑序。

• 将源点的early都置为0，按拓扑序计算v_early，并得到最大的v_early（关键路径长度）。

• ⚠️按逆拓扑序计算v_late。

  • 将early最大的汇点的late也设为同样的值。其他汇点的late需计算。
  • 遍历graph[curr][i]更新v_late对汇点无效，应该加一行v_late[curr] = min(max_path_weight, v_late[curr);
  • ❌将汇点的late都设为与early相等❌。这条不对，做下面一题发现的，此处代码没有改= =。

• 计算所有边的early和late，若边的early == late，这条边是关键路径上的边，放到关键路径图cg上。(代码里写的是反向存边，没必要 = =)

• dfs求关键路径，path是当前路径，vector<vector<int>> critical_paths是所有关键路径的集合。
  push_back, pop_back维护path，若到达early为0的点（源点），则push_back（path）到关键路径集合中。

• reverse每条path再排序，输出即可。

#include <cstdio>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <vector>

#define INF 0x3fffffff
using namespace std;
int nn, mm;
int graph[1001][1001], in_deg[1001] = {0}, out_deg[1001] = {0};
int v_early[1001], v_late[1001]; // init: -1, INF
map<pair<int, int>, pair<int, int>> edge_early_late; // init
queue<int> topo;
stack<int> rv_topo;
vector<int> srcs, targets, cg[1001]; // reverse_graph with only critical activities
int max_path_len = -1;
vector<int> path;
vector<vector<int>> critical_paths;

int topoSort() {
    int res = 0;
    bool in_topo[1001] = {false};
    while (res < nn) {
        int curr = -1;
        for (int i = 0; i < nn; ++i) {
            if (!in_topo[i] && in_deg[i] == 0) {
                curr = i;
                break;
            }
        }
        if (curr == -1) return res;
        in_topo[curr] = true;
        topo.push(curr);
        rv_topo.push(curr);
        res++;
        for (int i = 0; i < nn; i++) {
            if (graph[curr][i] != INF)
                in_deg[i]--;
        }
    }
    return nn;
}

void calc_V_early() { // topo
    while (!topo.empty()) {
        int curr = topo.front();
        topo.pop();
        for (int k = 0; k < nn; k++) {
            if (graph[k][curr] != INF) {
                v_early[curr] = max(v_early[curr], v_early[k] + graph[k][curr]);
            }
        }
        max_path_len = max(max_path_len, v_early[curr]);
    }
}

void calc_V_late() {
    for (auto item: targets)
        v_late[item] = v_early[item];
    while (!rv_topo.empty()) {
        int curr = rv_topo.top();
        rv_topo.pop();
        for (int i = 0; i < nn; ++i) {
            if (graph[curr][i] != INF) {
                v_late[curr] = min(v_late[curr], v_late[i] - graph[curr][i]);
            }
        }
    }
}

void calc_E_early_late() {
    for (auto &item: edge_early_late) {
        item.second.first = v_early[item.first.first];
        item.second.second = v_late[item.first.second]
                             - graph[item.first.first][item.first.second];
        if (item.second.first == item.second.second)
            cg[item.first.second].push_back(item.first.first);
    }
}

void dfs_critical_path(int root) {
    if (v_early[root] == 0) {
        path.emplace_back(root);
        critical_paths.emplace_back(path);
        path.pop_back();
        return;
    }
    path.emplace_back(root);
    for (auto &item: cg[root]) {
        dfs_critical_path(item);
    }
    path.pop_back();
}

int main() {
    scanf("%d%d", &nn, &mm);
    fill(graph[0], graph[0] + 1001 * 1001, INF);
    fill(v_early, v_early + 1001, -1);
    fill(v_late, v_late + 1001, INF);
    int v1, v2, weight;
    for (int i = 0; i < mm; ++i) {
        scanf("%d%d%d", &v1, &v2, &weight);
        graph[v1][v2] = weight;
        edge_early_late[make_pair(v1, v2)] = make_pair(0, 0);
        in_deg[v2]++;
    }
    for (int i = 0; i < nn; ++i) {
        if (in_deg[i] == 0) {
            srcs.emplace_back(i);
            v_early[i] = v_late[i] = 0;
        }
        if (out_deg[i] == 0) targets.emplace_back(i);
    }
    int topo_len = topoSort();
    if (topo_len < nn) {
        printf("NO %d", nn - topo_len);
    } else {
        calc_V_early();
        calc_V_late();
        calc_E_early_late();
        printf("YES %d\n", max_path_len);
        for (auto &item: targets) {
            if (v_early[item] == max_path_len) {
                dfs_critical_path(item);
            }
        }
        for (auto &item: critical_paths)
            reverse(item.begin(), item.end());
        sort(critical_paths.begin(), critical_paths.end());
        for (auto &i1: critical_paths) {
            int len = i1.size();
            for (int r = 0; r < len; r++) {
                printf("%d", i1[r]);
                printf(r == len - 1 ? "\n" : "->");
            }
        }
    }
    return 0;
}

1044 | 关键路径

注意点还是上面提过的那些。
⚠️⚠️auto遍历修改了容器内的值，必须！一定！要加&引用for (auto &item:edges_el)

• 这次没有智障的反向存边= = ，正常的存了边(只保留关键活动的新图)，然后dfs……
  新的边用map<int, set<int>> next存的话就能保证顺序，不用全部遍历完后排序了。。

#include <cstdio>
#include <map>
#include <vector>
#include <unordered_set>
#include <algorithm>

#define INF 0x3fffffff
using namespace std;
int nn, graph[1001][1001], in_deg[1001] = {0}, out_deg[1001] = {0}, v_early[1001], v_late[1001], max_path_weight = -1;
map<pair<int, int>, pair<int, int>> edges_el; //edge v1->v2 early, late
vector<vector<int>> paths;
vector<int> topo_seq, critical_graph[1001], temp_path;
unordered_set<int> srcs, targets;

bool topoSort() {
    bool inSeq[1001] = {false};
    for (int i = 0; i < nn; ++i) {
        int curr = -1;
        for (int j = 1; j <= nn; j++) {
            if (!inSeq[j] && in_deg[j] == 0) curr = j;
        }
        if (curr == -1) return false;
        inSeq[curr] = true;
        topo_seq.push_back(curr);
        for (int j = 1; j <= nn; ++j) {
            if (!inSeq[j] && graph[curr][j] != INF)
                in_deg[j]--;
        }
    }
    return true;
}

void calc_v_early() {
    for (int i = 0; i < nn; ++i) {
        int curr = topo_seq[i];
        for (int j = 1; j <= nn; ++j) {
            if (graph[j][curr] != INF)
                v_early[curr] = max(v_early[curr], v_early[j] + graph[j][curr]);
        }
        max_path_weight = max(max_path_weight, v_early[curr]);
    }
}

void calc_v_late() {
    for (auto item: targets) {
        if (v_early[item] == max_path_weight) v_late[item] = max_path_weight;
    }
    for (int i = nn - 1; i >= 0; --i) {
        for (int j = 1; j <= nn; ++j) {
            if (graph[topo_seq[i]][j] != INF)
                v_late[topo_seq[i]] = min(v_late[topo_seq[i]], v_late[j] - graph[topo_seq[i]][j]);
        }
        v_late[topo_seq[i]] = min(max_path_weight, v_late[topo_seq[i]]);
    }
}

void calc_e_el() {
    for (auto &item:edges_el) {
        item.second.first = v_early[item.first.first];
        item.second.second = v_late[item.first.second] - graph[item.first.first][item.first.second];
        if (item.second.first == item.second.second)
            critical_graph[item.first.first].push_back(item.first.second);
    }
}

// 一定无环
void DFS(int root) {
    if (critical_graph[root].empty()) {
        if (v_early[root] == max_path_weight) {
            temp_path.push_back(root);
            paths.push_back(temp_path);
            temp_path.pop_back();
        }
    }
    temp_path.push_back(root);
    for (auto item:critical_graph[root]) DFS(item);
    temp_path.pop_back();
}

int main() {
    int mm, v1, v2, tw;
    scanf("%d%d", &nn, &mm);
    fill(graph[0], graph[0] + 1001 * 1001, INF);
    fill(v_early, v_early + 1001, -1);
    fill(v_late, v_late + 1001, INF);
    for (int i = 0; i < mm; ++i) {
        scanf("%d%d%d", &v1, &v2, &tw);
        graph[v1][v2] = tw;
        in_deg[v2]++;
        out_deg[v1]++;
        edges_el[make_pair(v1, v2)] = make_pair(0, 0);
    }
    for (int i = 1; i <= nn; i++) {
        if (in_deg[i] == 0) {
            v_early[i] = 0;
            srcs.insert(i);
        }
        if (out_deg[i] == 0)
            targets.insert(i);
    }
    bool flag = topoSort();
    if (flag) {
        puts("YES");
        calc_v_early();
        calc_v_late();
        calc_e_el();
    }
    int nq;
    scanf("%d", &nq);
    for (int j = 0; j < nq; ++j) {
        scanf("%d%d", &v1, &v2);
        if (flag) printf("%d %d\n", edges_el[make_pair(v1, v2)].first, edges_el[make_pair(v1, v2)].second);
    }
    if (flag) {
        printf("%d\n", max_path_weight);
        for (auto item: srcs)
            DFS(item);
        sort(paths.begin(), paths.end());
        for (auto &item: paths) { // output path
            int len = item.size();
            for (int i = 0; i < len; ++i) {
                printf("%d", item[i]);
                printf(i + 1 == len ? "\n" : "->");
            }
        }
    }
    if (!flag) puts("NO");
    return 0;
}