题目链接： 最短工期 (25分)

拓扑排序

只适用于有向无环图
有向无环图一定有拓扑排序

核心算法：

  1. 把入度为0的点存放在队列里面
  2. 删除该顶点连接的所有边

解题步骤：

  1. 记录每个点的入度大小
  2. 把入度为0的点放入队列中去
  3. 用一个dist[]数组存放路径的大小，用cnt记录顶点个数
  4. 删除该顶点连接的所有边，即每条边对应的点的入度-1
  5. 再次把入度为0的点存放在队列里面
  6. 更新dist[]数组的大小，存放路径最长的

如果记录的顶点个数小于该图中的顶点个数，则该图中存在回路，不能实现拓扑排序

代码如下：

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>

using namespace std;

const int N = 110;

#define mm(a,x) memset(a,x,sizeof a)
#define inf 0x3f3f3f3f

int mp[N][N],d[N],dist[N];
int n,m;
int ans;

int topsort(){
    queue<int > q;
    int cnt = 0;
    for(int i = 0; i < n; i ++ ){
        if(d[i] == 0) q.push(i);
    }
    while(q.size()){
        int t = q.front();
        q.pop();
        cnt ++;
        if(dist[t] > ans) ans = dist[t]; 
        for(int i = 0; i < n; i ++ ){
            if(mp[t][i] != inf){
                d[i] --;
                if(d[i] == 0) q.push(i);
                if(dist[i] < dist[t] + mp[t][i]){
                    dist[i] = dist[t] + mp[t][i];
                }
            }
        }
    }
    if(cnt < n) return 0;
    else return ans;
}
int main(){
    cin >> n >> m;
    mm(mp,inf);
    for(int i = 0; i < m; i ++ ){
        int a,b,c; cin >> a >> b >> c;
        mp[a][b] = c;
        d[b] ++;
    }
    int t = topsort();
    if(t == 0) cout<<"Impossible\n";
    else cout<<t;    
    return 0;
}