08-图8 How Long Does It Take

08-图8 How Long Does It Take

分数 25
作者 陈越
单位 浙江大学

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.

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

代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
C++ (g++)

思路：

典型的拓扑排序问题，先把所有入度为0的点入队，进入循环，每次弹出一个节点，找出与这个节点相连的节点，入度减1，更新最小花费时间，再把所有入度为0的节点入列，进入下一次循环。用cnt判断有没有环。

AC代码：

#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 cnt=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();
        cnt++;
        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(cnt!=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;
}