算法——图论——关键活动
原题
#include <iostream>
#include <vector>
#include <queue>
#include <set>
using namespace std;
struct edge {
int destination;
int dist;
edge(int destination_, int dist_) : destination(destination_), dist(dist_) {}
};
vector<edge> graph[100];
vector<edge> reGraph[100];
vector<int> inDo(100, 0);
vector<int> outDo(100, 0);
vector<int> lessTime(100, 0);
vector<int> moreTime(100, 0x3fffffff);
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
graph[u].emplace_back(v, w);
reGraph[v].emplace_back(u, w);
outDo[u]++;
inDo[v]++;
}
queue<int> q;
for (int i = 0; i < n; ++i) {
if (inDo[i] == 0) {
q.push(i);
lessTime[i] = 0;
}
}
while (!q.empty()) {
int cur = q.front();
q.pop();
for (edge neighbor: graph[cur]) {
inDo[neighbor.destination]--;
lessTime[neighbor.destination] = max(lessTime[neighbor.destination], lessTime[cur] + neighbor.dist);
if (inDo[neighbor.destination] == 0) {
q.push(neighbor.destination);
}
}
}
int totalTime = 0;
for (int i = 0; i < n; ++i) {
if (inDo[i] != 0) {
cout << "No" << endl;
return 0;
}
totalTime = max(totalTime, lessTime[i]);
}
for (int i = 0; i < n; ++i) {
if (outDo[i] == 0) {
q.push(i);
moreTime[i] = totalTime;
}
}
while (!q.empty()) {
int cur = q.front();
q.pop();
for (edge neighbor: reGraph[cur]) {
outDo[neighbor.destination]--;
moreTime[neighbor.destination] = min(moreTime[neighbor.destination], moreTime[cur] - neighbor.dist);
if (outDo[neighbor.destination] == 0) {
q.push(neighbor.destination);
}
}
}
set<pair<int, int>> s;
for (int i = 0; i < n; ++i) {
for (edge neighbor: graph[i]) {
if (moreTime[neighbor.destination] - lessTime[i] - neighbor.dist == 0) {
s.insert({i, neighbor.destination});
}
}
}
// for (int i = 0; i < n; ++i) {
// if (lessTime[i] == 0 && moreTime[i] == 0) {
// q.push(i);
// }
// }
// while (!q.empty()) {
// auto cur = q.front();
// q.pop();
// for (auto neighbor: graph[cur]) {
// if (lessTime[neighbor.destination] == moreTime[neighbor.destination]) {
// s.insert({cur, neighbor.destination});
// q.push(neighbor.destination);
// }
// }
// }
cout << "Yes" << endl;
for (auto p: s) {
cout << p.first << " " << p.second << endl;
}
return 0;
}