《数据结构》08-图8 How Long Does It Take

今天药忘吃喽~ 2022-04-16 07:07 161阅读 0赞

# 题目 #

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

# 分析 #

考察拓扑排序  
每次更新一个点时，更新其周围邻接点的时间  
最后输出时，也许有多个终点，输出时间最大的，即为项目最早完成时间

#include<iostream>
    #include<queue>
    #include <algorithm>
    #define MaxVertex 105
    #define INF -100000
    typedef int Vertex;
    using namespace std;
    int N; // 点
    int M;  // 边
    int G[MaxVertex][MaxVertex];  
    int Earliest[MaxVertex];  // 时间 
    int Indegree[MaxVertex]; // 入度 
    
    // 初始化图 
    void build(){
        
    	Vertex v1,v2,w;
    	cin>>N>>M;
    	for(Vertex i=0;i<N;i++){
        
    		for(Vertex j=0;j<N;j++)
    			G[i][j] = INF;
    	}
    	for(int i=0;i<M;i++){
        
    		cin>>v1>>v2>>w;
    		G[v1][v2] = w;  // 有向图 
    		Indegree[v2]++;  // 入度+1 
    	}
    }
    
    void TopSort(){
        
    	int cnt = 0;
    	queue<Vertex> q;
    	// 入度为0顶点入队 
    	for(Vertex i=0;i<N;i++)
    		if(!Indegree[i]){
         
    			q.push(i);
    			Earliest[i] = 0;
    		} 
    	while(!q.empty()){
        
    		Vertex v = q.front();
    		q.pop();
    		cnt++;
    		for(Vertex w=0;w<N;w++)
    			if(G[v][w]!=INF){
         
    				if(Earliest[w] < Earliest[v]+G[v][w])  //如果周围有时间更长，更新时间 
    					Earliest[w] = max(Earliest[w],Earliest[v]+G[v][w]);
    				if(--Indegree[w]==0)
    					q.push(w);
    			} 
    	}
    	if(cnt!=N)
    		cout<<"Impossible";
    	else{
         
    		// 也许不止一个终点 
    		int max = 0;
    		for(Vertex i=0;i<N;i++)  
    			if(max < Earliest[i]) 
    				max = Earliest[i];
    		cout<<max;
    	}
    		
    }
    
    int main(){
        
    	build();
    	TopSort();
    	return 0;
    }