(!!!重要)关键路径
题目大意
给出整个项目中各个活动的优先关系和完成时长，求出完成项目的最短时间和关键路径。关键活动输出的顺序规则是：任务开始的交接点编号小者优先，起点编号相同时，与输入时任务的顺序相反。
思路
题目要求起点编号相同时输出的路径与输入相反，所以用一个二位数组s记录输入的顺序，s[u][v]表示u->v出现的顺序，从1开始标号。 先用拓扑排序求出拓扑序列，存在一个栈中，同时求事件的最早发生时间ve。再根据逆拓扑序列（即出栈顺序），更新时间的最迟发生时间vl。 对于每一个活动（边u->v），最早开始时间e=ve[u]；最迟开始时间l=vl[v]-w(即u->v边权)。若e与l相等，则是关键路径，把他加入一个结构体变长数组ans中。这里注意要记得删掉之前加入超级源点和超级汇点时引入的长度为0的边。最后根据要求排序。
AC代码
#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
using namespace std;
#define MAX 105
struct node {
int v, w;
};
struct ANS {
int v1, v2, index;
};
vector<node>G[MAX];
vector<ANS>ans;
stack<int>topoOrder;
int n, m, start, ending;
int in[MAX] = { 0 }, ve[MAX] = { 0 }, vl[MAX], s[MAX][MAX] = { 0 };
int topo() {
queue<int>q;
q.push(start);
while (!q.empty()) {
int u = q.front();
q.pop();
topoOrder.push(u);
for (int i = 0;i < G[u].size();i++) {
int v = G[u][i].v, w = G[u][i].w;
in[v]--;
if (in[v] == 0)q.push(v);
if (ve[v] < ve[u] + w)ve[v] = ve[u] + w;
}
}
if (topoOrder.size() == n)return ve[ending];
else return -1;
}
bool cmp(ANS a, ANS b) {
if (a.v1 == b.v1) return a.index > b.index;
else return a.v1 < b.v1;
}
void Critical() {
if (topo() == -1) { printf("0"); return; }
fill(vl, vl + n + 1, ve[ending]); //注意结点标号是1到n，所以这里第二个参数是v1+n+1。
while (!topoOrder.empty()) {
int u = topoOrder.top();
topoOrder.pop();
//由后继结点来更新当前结点
for (int i = 0;i < G[u].size();i++) {
int v = G[u][i].v;
if (vl[u] > vl[v] - G[u][i].w)
vl[u] = vl[v] - G[u][i].w;
}
}
for (int u = 1;u <= n;u++) {
for (int i = G[u].size() - 1;i >= 0;i--) {
int v = G[u][i].v, w = G[u][i].w;
int e = ve[u], l = vl[v] - w;
if (e == l && w != 0) {//要记得把边权为0的边（即创造超级源/汇点时创造的边）删去
ANS temp;
temp.v1 = u;temp.v2 = v;
temp.index = s[u][v];
ans.push_back(temp);
}
}
}
sort(ans.begin(), ans.end(), cmp);
printf("%d\n", ve[ending]);
for (int i = 0;i < ans.size();i++)
printf("%d->%d\n", ans[i].v1, ans[i].v2);
}
int main() {
node temp;
scanf("%d%d", &n, &m);
for (int i = 0;i < m;i++) {
scanf("%d%d%d", &start, &temp.v, &temp.w);
G[start].push_back(temp);
in[temp.v]++;
s[start][temp.v] = i + 1;
}
//若有多个源点或汇点，则建立超级源点或超级汇点，保证源点或汇点只有一个。
int numin = 0, numout = 0;
for (int i = 1;i <= n;i++) {
if (in[i] == 0) {
numin++;
start = i;
}
if (G[i].size() == 0) {
numout++;
ending = i;
}
}
if (numin > 1) {
n++;
start = n;temp.w = 0;
for (int i = 1;i < n;i++) {
if (in[i] == 0) {
temp.v = i;
G[start].push_back(temp);
in[i] = 1;
}
}
}
if (numout > 1) {
n++;
ending = n; in[ending] = numout;//不要忘记修改in[ending]的值噢~
temp.w = 0; temp.v = ending;
for (int i = 1;i < n;i++) {
if (G[i].size() == 0) G[i].push_back(temp);
}
}
Critical();
return 0;
}
