08-图8 How Long Does It Take

一、题目

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 (≤), 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

二、思路

规规矩矩的拓扑排序

三、参考代码

#include <stdlib.h> 
#include <cstdio>
#include <queue>
#define MaxVertexNum 102
#define INFINITY 65536
using namespace std;

typedef int Vertex;         
typedef int WeightType;        
typedef int DataType;       

int Indegree[MaxVertexNum];


typedef struct ENode *Edge;
struct ENode{
    Vertex V1, V2;      
    WeightType Weight;  
};

typedef struct AdjVNode *PtrToAdjVNode; 
struct AdjVNode{
    Vertex AdjV;       
    WeightType Weight;  
    PtrToAdjVNode Next;   
};
 
typedef struct Vnode{
    PtrToAdjVNode FirstEdge;
    DataType Data;            
} AdjList[MaxVertexNum];    /* AdjListÊÇÁÚ½Ó±íÀàÐÍ */
 
 

typedef struct GNode *LGraph;
struct GNode{  
    int Nv;     
    int Ne;     
    AdjList G; 
};



LGraph CreateGraph( int VertexNum );
void InsertEdge( LGraph Graph, Edge E );
LGraph BuildGraph();
bool topSort(LGraph Graph);

void find_max(LGraph Graph);

int main() {
    LGraph Graph = BuildGraph();
    
    if( !topSort(Graph) ) printf("Impossible\n");
    else {
        find_max(Graph);
    }

    
}

LGraph CreateGraph( int VertexNum )
{ 
    Vertex V;
    LGraph Graph;
     
    Graph = (LGraph)malloc( sizeof(struct GNode) ); 
    Graph->Nv = VertexNum;
    Graph->Ne = 0;
    
       for (V=0; V<Graph->Nv; V++)
        Graph->G[V].FirstEdge = NULL;
             
    return Graph; 
}      
void InsertEdge( LGraph Graph, Edge E )
{
    PtrToAdjVNode newNode = new AdjVNode;
    newNode->Weight = E->Weight;
    newNode->AdjV = E->V2;
    
    newNode->Next = Graph->G[E->V1].FirstEdge;
    Graph->G[E->V1].FirstEdge = newNode;
         

}
LGraph BuildGraph()
{
    LGraph Graph;
    int Nv;
    Edge E;
    Vertex V;
    
    scanf("%d", &Nv);
    Graph = CreateGraph(Nv);
    
    scanf("%d", &(Graph->Ne));
    
    if(Graph->Ne) {
        E = new ENode;
        for(int i=0; i<Graph->Ne; i++) {
            scanf("%d %d %d", &(E->V1), &(E->V2), &(E->Weight));
            InsertEdge(Graph, E);
        } 
    }
    
    for(V=0; V<Graph->Nv; V++) {
        Graph->G[V].Data = 0;
    }
    return Graph;
  
}
bool topSort(LGraph Graph) 
{
    int cnt;
    Vertex V;
    queue<Vertex> Q;
    
    cnt = 0;
    for( V=0; V<Graph->Nv; V++) Indegree[V] = 0;
    
    for( V = 0; V < Graph->Nv; V++) {
        for(PtrToAdjVNode W = Graph->G[V].FirstEdge; W; W=W->Next) {
            Indegree[W->AdjV]++;
            Graph->G[W->AdjV].Data = 0;
        }
    }
    for(V=0; V<Graph->Nv; V++) if(Indegree[V] == 0) Q.push(V);
    
    while(!Q.empty()) {
        V = Q.front();
        Q.pop();
        cnt++;
        
        for(PtrToAdjVNode W = Graph->G[V].FirstEdge; W; W=W->Next) {
            if(--Indegree[W->AdjV] == 0) Q.push(W->AdjV);
            if(Graph->G[W->AdjV].Data < W->Weight + Graph->G[V].Data) 
                Graph->G[W->AdjV].Data =  W->Weight + Graph->G[V].Data;
            
        }
        
        
    }
    
    if(cnt != Graph->Nv) return false;
    return true;
    

}

void find_max(LGraph Graph)
{
    Vertex V;
    int compTime;
    compTime = Graph->G[0].Data;
    
    for(V = 1; V < Graph->Nv; V++) {
        if(Graph->G[V].Data > compTime) compTime = Graph->G[V].Data;
    }
    printf("%d\n", compTime);
}