第一次写关键路径的题，交上去直接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;
}
网友评论