拓扑排序

  • 图中每个顶点只出现一次。
  • A在B前面，则不存在B在A前面的路径。(不能成环！！！！)
  • 顶点的顺序是保证所有指向它的下个节点在被指节点前面！(例如A—>B—>C那么A一定在B前面，B一定在C前面)。所以，这个核心规则下只要满足即可，所以拓扑排序序列不一定唯一！
  1. 计算各节点的入度，把所有为0的（也就是起点）放入栈中
  2. 每次经过节点，节点的入度减一，入度为0入栈
  3. 把每条路 入的最长时间放入数组中
  4. 数组中最大的数就是最长时间
本题是从起始点到终点最长的距离。

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 12
0 1 6
0 2 4
0 3 5
1 4 1
2 4 1
3 5 2
5 4 0
4 6 9
4 7 7
5 7 4
6 8 2
7 8 4

Sample Output 1:

18

Sample Input 2:

4 5
0 1 1
0 2 2
2 1 3
1 3 4
3 2 5

Sample Output 2:

Impossible

代码

#include<bits/stdc++.h>
using namespace std;
#define maxn 10000
#define ma 65535
int 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;
}