拓扑排序
图中每个顶点只出现一次。A在B前面，则不存在B在A前面的路径。(不能成环！！！！)顶点的顺序是保证所有指向它的下个节点在被指节点前面！(例如A—>B—>C那么A一定在B前面，B一定在C前面)。所以，这个核心规则下只要满足即可，所以拓扑排序序列不一定唯一！ 计算各节点的入度，把所有为0的（也就是起点）放入栈中每次经过节点，节点的入度减一，入度为0入栈把每条路 入的最长时间放入数组中数组中最大的数就是最长时间本题是从起始点到终点最长的距离。
08-图8 How Long Does It Take (25分)
08-图8需要多长时间
Given the relations of all the activities of a project, you are supposed to find the earliest completion time of the project.
给定项目所有活动的关系，您应该找到项目的最早完成时间。
Input Specification:
Each input file contains one test case. Each case starts with a line containing two positive integers N (≤100), the number of activity check points (hence it is assumed that the check points are numbered from 0 to N−1), and M, the number of activities. Then M lines follow, each gives the description of an activity. For the i-th activity, three non-negative numbers are given: S[i], E[i], and L[i], where S[i] is the index of the starting check point, E[i] of the ending check point, and L[i] the lasting time of the activity. The numbers in a line are separated by a space.
每个输入文件包含一个测试用例。每种情况都从包含两个正整数N（≤100）的行开始，N是活动性检查点的数目（因此，假设检查点的编号是从0到N-1），而M是活动性数目。然后紧跟着M行，每行给出了活动的描述。对于第i个活动，给出了三个非负数：S [i]，E [i]和L [i]，其中S [i]是起始检查点的索引，E [i]为结束检查点，L [i]活动的持续时间。一行中的数字用空格分隔。
Output Specification:
For each test case, if the scheduling is possible, print in a line its earliest completion time; or simply output “Impossible”.
对于每个测试用例，如果可以安排时间，请在一行中打印其最早完成时间；或简单地输出“不可能”
Sample Input 1:
9 120 1 60 2 40 3 51 4 12 4 13 5 25 4 04 6 94 7 75 7 46 8 27 8 4
Sample Output 1:
18
Sample Input 2:
4 50 1 10 2 22 1 31 3 43 2 5
Sample Output 2:
Impossible
代码
#include<bits/stdc++.h>using namespace std;#define maxn 10000#define ma 65535int a[maxn][maxn];int n,m;int visited[maxn]={0};int aa[maxn]={0};int sum=0;void findMax(){for(int i=0;i<n;i++){if(sum<aa[i]){sum=aa[i];}}}int TopSort(){stack<int> q;int count=0;for(int i=0;i<n;i++){//计算各结点的入度for(int j=0;j<n;j++){if(a[i][j]!=ma){visited[j]++;}}}for(int i=0;i<n;i++){//入度为0的入队if(visited[i]==0){q.push(i);}}while(!q.empty()){int v=q.top();q.pop();count++;for(int i=0;i<n;i++){if(a[v][i]!=ma){if(aa[v]+a[v][i]>aa[i]){//入路最长时间进数组aa[i]=aa[v]+a[v][i];}if(--visited[i]==0){//入度减为0入栈q.push(i);}}}}findMax();if(count!=n){return 0;}else{return 1;}}int main(){cin>>n>>m;for(int i=0;i<n;i++){for(int j=0;j<n;j++){a[i][j]=ma;}}int q,w,e;for(int i=1;i<=m;i++){cin>>q>>w>>e;a[q][w]=e;}int aaa=TopSort();if(aaa==0){cout<<"Impossible";}else{cout<<sum;}return 0;}
如果觉得《08-图8 How Long Does It Take（拓扑排序）》对你有帮助，请点赞、收藏，并留下你的观点哦！
