浙大数据结构：08-图8 How Long Does It Take

这道题算是较为简单的拓扑排序题，难度不大
机翻

1、条件准备

n,m为n个结点，m条边。
tim数组存到该结点完成的最早时间，会一点点更新
graph存有向边的时间
indegree数组存每个结点的入度

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

2、主函数

初始化graph为-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]++;graph[s][e]=l;
}
tuopu();return 0;
}

3、tuopu函数

还是用数组模拟队列存储入度为0的结点。
先遍历一遍把入度为0的结点加入队列
遍历队列，取队头元素，看它到其它结点有没有路径，
有的话更新tim，可达结点的tim变为当前结点的完成时间和本身的较大值，–入度，如果为0就加入队列。
最后如果入队的元素不为结点数量输出Impossible
否则遍历一遍timm数组，输出最大值

void tuopu()
{int q[105];int hh=0,tt=-1;//数组模拟队列for(int i=0;i<n;i++)if(indegree[i]==0)q[++tt]=i;while(hh<=tt){int cur=q[hh++];for(int i=0;i<n;i++){if(graph[cur][i]<0)continue;tim[i]=max(tim[i],tim[cur]+graph[cur][i]);if(--indegree[i]==0)q[++tt]=i;}}int answer=0;if(tt!=n-1){cout<<"Impossible";return ;}for(int i=0;i<n;i++)answer=max(answer,tim[i]);cout<<answer;
}

4、总结

这道题算是拓扑排序较易题，难度不大
完整代码如下

#include <iostream>
#include <vector>
#include<string.h>
using namespace std;
#define endl '\n'int n,m;
int tim[105];
int graph[105][105];
int indegree[105];
void tuopu()
{int q[105];int hh=0,tt=-1;//数组模拟队列for(int i=0;i<n;i++)if(indegree[i]==0)q[++tt]=i;while(hh<=tt){int cur=q[hh++];for(int i=0;i<n;i++){if(graph[cur][i]<0)continue;tim[i]=max(tim[i],tim[cur]+graph[cur][i]);if(--indegree[i]==0)q[++tt]=i;}}int answer=0;if(tt!=n-1){cout<<"Impossible";return ;}for(int i=0;i<n;i++)answer=max(answer,tim[i]);cout<<answer;
}
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]++;graph[s][e]=l;
}
tuopu();return 0;
}