AOE 토폴로지 정렬 + 최 단 공사 기간 + 각 변 의 기동 시간 + 관건 적 인 경 로 를 얻 기 08 - 그림 9 관건 적 인 활동 (30 분)

08 - 그림 9 관건 이벤트 (30 분)
하나의 프로젝트 가 한 조 의 하위 임무 로 구성 된다 고 가정 하면 하위 임무 간 에 어떤 것 은 병행 하여 집행 할 수 있 고, 어떤 것 은 반드시 다른 일부 하위 임 무 를 완성 한 후에 야 집행 할 수 있다.'작업 스케줄 링' 은 하위 작업 그룹 과 모든 하위 작업 이 의존 하 는 하위 작업 집합 을 수행 할 수 있 습 니 다.
예 를 들 어 한 학과 의 모든 과정 학습 과 졸업 디자인 을 완성 하면 학부생 이 완성 해 야 할 공사 로 볼 수 있 고 각 과정 은 하위 임무 로 볼 수 있다.일부 과정 은 영어 와 C 프로 그래 밍 등 을 동시에 개설 할 수 있 는데 그들 은 반드시 어떤 것 을 먼저 배 워 야 하 는 제약 이 없다.일부 과정 은 동시에 개설 할 수 없다. 왜냐하면 그들 은 선후 적 인 의존 관계 가 있 기 때문이다. 예 를 들 어 C 프로 그래 밍 과 데이터 구조 두 과목 은 반드시 전 자 를 먼저 배 워 야 한다.
그러나 주의해 야 할 것 은 한 그룹의 하위 임무 에 대해 임의의 임무 스케줄 이 모두 실행 가능 한 방안 이 아니 라 는 것 이다.예 를 들 어 방안 에 '하위 임무 A 는 하위 임무 B 에 의존 하고 하위 임무 B 는 하위 임무 C 에 의존 하 며 하위 임무 C 는 하위 임무 A 에 의존한다' 는 것 이 존재 한다. 그러면 이 세 가지 임 무 는 어느 것 도 먼저 수행 할 수 없다. 이것 은 실행 할 수 없 는 방안 이다.
임무 스케줄 문제 에서 만약 에 모든 하위 임 무 를 완성 하 는 데 필요 한 시간 을 제시 했다 면 우 리 는 전체 공 사 를 완성 하 는 데 필요 한 가장 짧 은 시간 을 계산 할 수 있다.이런 하위 임무 중 일부 임 무 는 며칠 늦 추어 완성 하 더 라 도 전체적인 공사 기한 에 영향 을 주지 않 는 다.그러나 일부 임 무 는 반드시 제시간에 완성 해 야 한다. 그렇지 않 으 면 전체 프로젝트 의 공사 기한 이 지연 되 고 이런 임 무 를 '관건 적 인 활동' 이 라 고 부른다.
주어진 프로젝트 의 작업 스케줄 링 이 가능 한 지 프로그램 을 작성 하 십시오.이 스케줄 링 방안 이 가능 하 다 면 전체 프로젝트 를 완성 하 는 데 필요 한 최 단 시간 을 계산 하고 모든 관건 적 인 활동 을 출력 합 니 다.
입력 형식: 첫 번 째 줄 에 두 개의 정수 N (≤ 100) 과 M 을 입력 하 십시오. 그 중에서 N 은 임무 인수 인계 점 (즉, 서로 의존 하 는 두 개의 하위 임 무 를 연결 하 는 노드 입 니 다. 예 를 들 어 임무 2 가 임무 1 을 완성 한 후에 야 시작 하려 면 두 임무 사이 에 반드시 인수 인계 점 이 있어 야 합 니 다) 의 수량 입 니 다.인수 인계 점 은 1N 번호 로 M 은 하위 임무 의 수량 이 고 순서대로 1M 이다.그 다음 에 M 줄 은 각 줄 에 3 개의 정 수 를 주 었 는데 그것 이 바로 이 임무 의 시작 과 완성 과 관련 된 인수 인계 점 번호 와 이 임무 에 필요 한 시간 이 고 정수 간 은 빈 칸 으로 구분 되 었 다.
출력 형식: 작업 스케줄 이 실행 되 지 않 으 면 0 을 출력 합 니 다.그렇지 않 으 면 첫 번 째 줄 의 출력 이 전체 프로젝트 를 완성 하 는 데 필요 한 시간 입 니 다. 두 번 째 줄 은 모든 관건 적 인 활동 을 출력 하기 시작 합 니 다. 모든 관건 적 인 활동 은 한 줄 을 차지 하고 형식 에 따라 'V - > W' 로 출력 합 니 다. 그 중에서 V 와 W 는 이 작업 의 시작 과 완성 과 관련 된 인수 인계 점 번호 입 니 다.관건 적 인 활동 출력의 순서 규칙 은 작업 이 시 작 된 인수 인계 점 번호 가 작은 사람 이 우선 이 고 기점 번호 가 같 으 며 입력 할 때 작업 의 순서 와 상반 된다 는 것 이다.
입력 예시:

7 8
1 2 4
1 3 3
2 4 5
3 4 3
4 5 1
4 6 6
5 7 5
6 7 2

출력 예시:

17
1->2
2->4
4->6
6->7

AOE 토폴로지 정렬 의 종합 적 인 문 제 는 총 공사 기한 과 모든 임무 의 기동 시간 을 구 할 수 있다.
각 변 은 하나의 항목 을 대표 한다.모든 결산 점 은 하나의 임무 인수 인계 점 을 대표 한다.1. 각 변 의 최 단 공사 기한 을 구한다.2. 거꾸로 각 시 에 가장 먼저 시작 하 는 시간 을 구한다.3. 이들 은 서로 감소 하여 각 임무 의 기동 시간 을 얻 고 순서대로 기동 시간 이 0 인 임 무 를 출력 하 는 것 이 관건 적 인 경로 이다.
A 【 】 【 】 각 퀘 스 트 에 필요 한 시간 을 저장 합 니 다.D 【 】 【 】 각 퀘 스 트 의 기동 시간 을 저장 합 니 다.Earliest 【 】 각 노드 의 최초 시작 시간 을 저장 합 니 다.Latest 【 】 각 노드 의 가장 늦 은 시작 시간 을 저장 합 니 다.현재 한 결산 점 의 최초 시작 시간 + 이 임무 에 필요 한 시간 = 뒤의 결산 점 의 가장 늦 은 시작 시간 은 이 임무 의 기동 시간 이 0, 즉 관건 적 인 임무 임 을 설명 한다.
1. main 함수

#include
#include
using namespace std;

#define MAX 105
#define INFINITY 65535

int N,M,A[MAX][MAX],ECT,EarliestTime[MAX]={0},LatestTime[MAX],D[MAX][MAX],idx;

퀘 스 트 에 소요 되 는 시간 을 A 【 】 【 】 에 저장 하고 각 퀘 스 트 의 기동 시간 을 inf 로 초기 화 합 니 다.TopSort_Earliest (), 각 퀘 스 트 의 최초 종료 시간 을 계산 합 니 다.그리고 임무 수 를 통계 하여 그림 의 연결 여 부 를 판단 한다.TopSort_latest (), 각 퀘 스 트 의 가장 늦 은 시작 시간 을 계산 합 니 다.PrintKeyRoute () 함수 가 관건 적 인 작업 을 하나씩 출력 합 니 다.

int main(){
	int a,b;
	scanf("%d %d",&N,&M);
	
	//      A        
	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
			D[i][j]=A[i][j]=INFINITY;
			
	//     A 
	for(int i=0;i<M;i++)
	{
		scanf("%d %d",&a,&b);
		scanf("%d",&A[--a][--b]); //   1  ，   0   
	}
	if(!TopSort_Earliest())
		printf("0
");
	else{
		printf("%d
",ECT);
		TopSort_Latest();
		PrintKeyRoute();
	}
	
} 

2. getMax 함 수 는 Earliest 의 최대 값 을 얻 고 아래 표 시 를 저장 합 니 다.종점 의 최초 종료 시간 은 각 점 의 최초 종료 시간의 최대 값 이다.이 종점 을 찾 아 최대 값 을 저장 합 니 다. 첫 번 째 출력 에 사용 합 니 다.

int getMax(int arr[])      //           
{
	int max=0;
	for (int i=0;i<N;i++)
		if(max<arr[i])
			{
				max=arr[i];     //        
				idx=i;       //         
			}
	return max;	
}

3. Earliest 함 수 는 그림 A 에 대한 입 도 를 계산한다.입 도 0 의 결산 점 을 입 대 했 습 니 다.순환 에 들 어가 기: 팀 의 첫 번 째 팀 에서 나 와 퀘 스 트 수 cnct + + 를 기록 하고 쌓 인 노드 뒤에 인접 한 퀘 스 트 를 옮 겨 다 니 며 노드 를 완성 합 니 다. 만약 에 현재 노드 에 퀘 스 트 시간 이 다음 노드 의 시작 시간 보다 많 으 면 다음 노드 의 시작 시간 을 큰 값 으로 업데이트 합 니 다.그리고 입 도 – 후 0 의 결산 점 을 입 대 했 습 니 다.

int TopSort_Earliest(){
	int V,cnt = 0, Indegree[MAX] = {0};
	queue<int> q; 
	//       
	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
			if(A[i][j]!=INFINITY)
				Indegree[j]++;
	
	//     0   
	for(int i=0;i<N;i++)
		if(Indegree[i]==0)
			q.push(i);
			
	while(!q.empty()){
		V = q.front();     //       
		q.pop();
		cnt++;       //     
		for(int j=0;j<N;j++)
			if(A[V][j]!=INFINITY){    //  V     
				if(EarliestTime[V]+A[V][j]>EarliestTime[j]){
			//         
					EarliestTime[j]=EarliestTime[V]+A[V][j];
				}
				if(--Indegree[j]==0)
				//        0，   
					q.push(j); 
			}	
	}
	ECT=getMax(EarliestTime);       //      ——      
	if(cnt!=N) return 0;   //       
	else return 1;        
}
// Earlist            

마지막 으로 getmax 는 종점 의 아래 표 와 최대 치 를 얻 고 cnct 로 그림 이 연결 되 는 지 여 부 를 판단 합 니 다.
4. Latest 함 수 는 각 노드 의 가장 늦 은 시작 시간 을 계산한다.끝 정점 idx 에서 되 돌리 기;각 결점 의 출 도 를 계산 하여 출 도 0 의 입 대 를 한다.종료 정점 의 최초 종료 시간 초기 화;시작 순환: 각 팀 에서 나 와 이 노드 의 모든 전구 결점 을 옮 겨 다 니 며 앞의 결점 의 시작 시간 은 현재 노드 의 시작 시간 에서 이전 임무 의 소요 시간의 최소 치 를 뺀 다. 즉, 일찍 시작 할 수록 좋다.반드시 < = 을 사용 해 야 합 니 다. 그 밖 에 D 배열 컴퓨터 가 움 직 이 는 시간 이 필요 합 니 다. 즉, 앞의 노드 의 시작 시간 + 작업 시간 이 딱 맞습니다 = 현재 노드 의 시작 시간 은 이 작업 이 기동 시간 이 없습니다.마지막 으로 이 점 을 삭제 한 후 0 의 결산 점 으로 입 대 됩 니 다.

void TopSort_Latest(){
	int V,Outdegree[MAX] = {0};  //      0 
	queue<int> q;
				//        
	for(int i=0; i<N; i++)
		for(int j=0;j<N;j++)
			if(A[i][j]!=INFINITY)
				Outdegree[i]++;      //     
	//   0   
	for(int i=0;i<N;i++)
		if(Outdegree[i]==0)
			q.push(i);

	//   latesttime
	for(int i=0;i<N;i++)
		LatestTime[i]=INFINITY;
	
	LatestTime[idx]=ECT; //idx          ；ECT        
	//     
	while(!q.empty())
	{
		V=q.front();
		q.pop();
		//cnt++          ，cnt  
		for(int j=0;j<N;j++)
			if(A[j][V]!=INFINITY){    //  V      
				if(LatestTime[V]-A[j][V]<=LatestTime[j]){
					//         ，               
//   <=, 
					LatestTime[j]=LatestTime[V]-A[j][V];
					
					D[j][V]=LatestTime[V]-EarliestTime[j]-A[j][V];
			//D     ： V       -（j       +j V     ）
			//j       +j v        v       ，   
			// j v      ， j-v          
				} 
				if(--Outdegree[j]==0)
					q.push(j);
			} 
	 } 
} 

5. 출력 함수

void PrintKeyRoute()
{
	for(int i=0;i<N;i++)    //               
		for(int j=N-1;j>=0;j--)    //       ，           。
			if(D[i][j]==0)
				printf("%d->%d
",i+1,j+1); 
}

관건 적 인 경로 인 기동 시간 이 0 인 임무 경 로 를 정리 하면 여러 가지 가 있 을 수 있다.관건 적 인 경 로 를 구 하려 면 먼저 가장 빠 른 종료 시간 을 구하 고 가장 늦 은 시작 시간 을 구 해 야 한다.현재 점 종료 시간 + 이 점 에서 시작 하 는 퀘 스 트 시간 = 다음 퀘 스 트 시작 시간 은 이 퀘 스 트 의 기동 시간 이 0 이면 관건 점 으로 출력 할 수 있 음 을 설명 합 니 다.