浙大数据结构：08-图9 关键活动

这道题还是有些麻烦的，主要是如何判断当前活动是关键活动，这里我们采用用紧后活动的最晚开始时间-当前活动的最早开始时间==活动所需时间来判断，想一想后面工作没法再拖了，而当前工作也尽早开始了，这样刚好干完的活动就是关键活动

1、条件准备

n表示结点数，m表示活动数。
earlytim数组表示最早开始时间，endtim数组表示最晚开始时间。
graph数组表示两节点间的活动持续时间是多少。
indegree数组表示每个结点的入度，outdegree数组表示

#include <iostream>
#include<string.h>
using namespace std;
#define endl '\n'int n,m;
int earlytim[105];
int endtim[105];
int graph[105][105];
int indegree[105];
int outdegree[105];

2、主函数

首先存图，初始化都为-1，表示俩结点间没有边。
循环输入数据，初始化结点的入度出度，时间存到graph数组里。
然后用拓扑排序

int main()
{std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>m;
memset(graph,-1,sizeof(graph));
while(m--)
{int s,e,l;cin>>s>>e>>l;indegree[e]++;outdegree[s]++;graph[s][e]=l;
}
tuopu();return 0;
}

3、tuopu函数

首先看看初始化每个活动的最早开始时间，用数组模拟队列，把入度为0的结点加入，更新每个结点的最早开始时间，取最大值。

 int q[105];int hh=0,tt=-1;//数组模拟队列for(int i=1;i<=n;i++)if(indegree[i]==0)q[++tt]=i;while(hh<=tt){int cur=q[hh++];for(int i=1;i<=n;i++){if(graph[cur][i]<0)continue;earlytim[i]=max(earlytim[i],earlytim[cur]+graph[cur][i]);if(--indegree[i]==0)q[++tt]=i;}}

然后先输出完成这个拓扑的最短时间，如果不行输出0

int finishtime=earlytim[q[tt]];if(tt!=n-1){  cout<<"0";return ;}cout<<finishtime<<endl;

然后逆向，算每个活动的最晚开始时间，先把出度为0的结点加入队列中，队列记得清空。初始化为finishtime。
取队头，如果有活动以该结点为终点，则更新前驱的最晚开始时间，取最小值，把出度为0的结点加入队列中

memset(endtim,1,sizeof(endtim));hh=0,tt=-1;for(int i=1;i<=n;i++)if(!outdegree[i]){q[++tt]=i;endtim[i]=finishtime;}while(hh<=tt){int cur=q[hh++];for(int i=1;i<=n;i++){if(graph[i][cur]<0)continue;endtim[i]=min(endtim[i],endtim[cur]-graph[i][cur]);if(--outdegree[i]==0)q[++tt]=i;}}

最后输出，遍历整个图，如果有路，并且当前活动的后继活动的最晚开始时间-该活动的最早开始时间==活动时间，则输出。

for(int i=1;i<=n;i++)//外层从小到大{for(int j=n;j>=1;j--)//内层从大到小{if(graph[i][j]<0)continue;if(endtim[j]-earlytim[i]==graph[i][j])cout<<i<<"->"<<j<<endl;}}

4、总结

这个题处理比较麻烦的是输出，该怎么判断该活动是不是关键活动。
完整代码如下：

#include <iostream>
#include<string.h>
using namespace std;
#define endl '\n'int n,m;
int earlytim[105];
int endtim[105];
int graph[105][105];
int indegree[105];
int outdegree[105];void tuopu()
{int q[105];int hh=0,tt=-1;//数组模拟队列for(int i=1;i<=n;i++)if(indegree[i]==0)q[++tt]=i;while(hh<=tt){int cur=q[hh++];for(int i=1;i<=n;i++){if(graph[cur][i]<0)continue;earlytim[i]=max(earlytim[i],earlytim[cur]+graph[cur][i]);if(--indegree[i]==0)q[++tt]=i;}}int finishtime=earlytim[q[tt]];if(tt!=n-1){  cout<<"0";return ;}cout<<finishtime<<endl;memset(endtim,1,sizeof(endtim));hh=0,tt=-1;for(int i=1;i<=n;i++)if(!outdegree[i]){q[++tt]=i;endtim[i]=finishtime;}while(hh<=tt){int cur=q[hh++];for(int i=1;i<=n;i++){if(graph[i][cur]<0)continue;endtim[i]=min(endtim[i],endtim[cur]-graph[i][cur]);if(--outdegree[i]==0)q[++tt]=i;}}for(int i=1;i<=n;i++)//外层从小到大{for(int j=n;j>=1;j--)//内层从大到小{if(graph[i][j]<0)continue;if(endtim[j]-earlytim[i]==graph[i][j])cout<<i<<"->"<<j<<endl;}}}
int main()
{std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>m;
memset(graph,-1,sizeof(graph));
while(m--)
{int s,e,l;cin>>s>>e>>l;indegree[e]++;outdegree[s]++;graph[s][e]=l;
}
tuopu();return 0;
}