How Long Does It Take (25分)【C语言】AOE拓扑排序

本文主要是介绍How Long Does It Take (25分)【C语言】AOE拓扑排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

Given the relations of all the activities of a project, you are supposed to find the earliest completion time of the project.

输入格式

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.

输出格式

For each test case, if the scheduling is possible, print in a line its earliest completion time; or simply output “Impossible”.

输入样例

输出样例

算法

AOE拓扑排序

入度为0的结点全部压入队列（如果是单一起点，压入指点结点即可）
while循环中弹出一个结点，对此节点的邻结点的入度减一（如果此邻结点入度减为0则直接入队）同时，更新此结点的earliest
根据处理的结点总数判断时间安排是否合理。合理时，在所有结点中选择最大的earliest输出

代码实现

int main()
{	int N,E;scanf("%d %d",&N,&E);Graph G=CreateGraph(N);BuildGraph(G,E);AOE(G);return 0;
}

AOE函数

入度为0的结点全部压入队列（如果是单一起点，压入指点结点即可）
while循环中弹出一个结点，对此节点的邻结点的入度减一（如果此邻结点入度减为0则直接入队）同时，更新此结点的earliest
根据处理的结点总数判断时间安排是否合理。合理时，在所有结点中选择最大的earliest输出

void AOE(Graph G)
{int *earliest=(int*)malloc(sizeof(int)*(G->VertexNum));//记录每个结点完成的最早时间 int *indegree=(int*)malloc(sizeof(int)*(G->VertexNum));//记录每个结点的入度 int i,j;for(i=0;i<G->VertexNum;i++){//初始化earliest，indegreeearliest[i]=-1;indegree[i]=0;for(j=0;j<G->VertexNum;j++){if(G->GraphMatrix[j][i]!=-1){indegree[i]++;}}}int *Queue=(int*)malloc(sizeof(int)*(G->VertexNum+1));int rear=0,head=0;int count=0;//当前收录到集合中元素个数 for(i=0;i<G->VertexNum;i++){//收录初始入度为0的结点if(indegree[i]==0){ Queue[rear++]=i;earliest[i]=0;}}int t,MaxVertex;while(rear>head){t=Queue[head++];count++;for(i=0;i<G->VertexNum;i++){if((G->GraphMatrix[t][i]!=-1)){if(--indegree[i]==0){Queue[rear++]=i;}if(earliest[i]<earliest[t]+G->GraphMatrix[t][i]){earliest[i]=earliest[t]+G->GraphMatrix[t][i];} }} }if(count==G->VertexNum){int MaxSchedule=0;for(i=0;i<G->VertexNum;i++){if(earliest[i]>MaxSchedule){MaxSchedule=earliest[i];}}printf("%d",MaxSchedule);}else{printf("Impossible");}
}

邻接矩阵存储的图

#define MAXVERTEXNUM 101
typedef struct GNode* Graph;
struct GNode{int VertexNum;int EdgeNum;int GraphMatrix[MAXVERTEXNUM][MAXVERTEXNUM];
};
typedef struct ENode* edge;
struct ENode{int V;int W;int Weight;
};
Graph CreateGraph(int N)
{Graph G=(Graph)malloc(sizeof(struct GNode));G->VertexNum=N;int i,j;for(i=0;i<N;i++){for(j=0;j<N;j++){G->GraphMatrix[i][j]=-1;}}return G;
}
void InsertEdge(Graph G,edge L)
{G->GraphMatrix[L->V][L->W]=L->Weight;
}
void BuildGraph(Graph G,int E)
{G->EdgeNum=E;edge L=(edge)malloc(sizeof(struct ENode));int i;for(i=0;i<E;i++){scanf("%d %d %d",&(L->V),&(L->W),&(L->Weight));InsertEdge(G,L);}free(L);
}