题目请点我 题解： 有一系列的工作需要做，可以同时做很多工作，但是某些特定工作之间需要一定的时间间隔。现在给出了这些时间间隔，问最短需要多长时间才能把所有的工作做完。因为时间上的限制，很容易想到拓扑排序。因为是按照时间去工作，可以想像把所有的工作都放到一个时间轴上去考虑，这样我们可以利用一个优先队列去维护。 每一次找到入读为1的点，然后去更新跟当前点连接有限制的点。如果被更新点的入度变为1，，则放入队列。 利用add数组将边的权值不断向后叠加，注意必须要满足的是最长的边。 测试数据： 5 3 1 2 100 1 3 2 3 4 2 5 3 1 4 5 1 3 2 3 4 1 5 3 1 4 2 1 3 5 3 4 5 7 6 1 2 3 1 3 4 2 4 5 3 4 6 4 5 7 4 6 8 代码实现：
using namespace std;struct node{int time;int pos;};int N,M;int result;int add[MAX_N];int time[MAX_N];int indegree[MAX_N];int cost[MAX_N][MAX_N];priority_queue<node> TD;//优先级按照时间排列bool operator < (const node a,const node b){return a.time < b.time;}//第一次放入队列void inTD();int main(){//freopen(“in.txt”,”r”,stdin);while( scanf(“%d%d”,&N,&M) != EOF ){result = 0;memset(cost,-1,sizeof(cost));memset(add,0,sizeof(add));memset(time,0,sizeof(time));memset(indegree,0,sizeof(indegree));while( !TD.empty() ){TD.pop();}int x,y,z;for( int i = 0; i < M; i++ ){scanf(“,&x,&y,&z);cost[x][y]=z;indegree[y]++;}inTD();while( !TD.empty() ){node start = TD.top();TD.pop();int pos = start.pos;//表示更新到当前节点时，当前节点的权值为之前最大的时间间隔time[pos] = add[pos];indegree[pos]–;//result保存所能检测到的最大时间间隔result = max(time[pos],result);for( int i = 0; i < N; i++ ){if( cost[pos][i] != -1 ){//更新最大时间间隔add[i] = max(time[pos]+cost[pos][i],add[i]);indegree[i]–;//若更新后入度为0就放入队列if( indegree[i] == 0 ){node tmp;tmp.pos = i;tmp.time = time[i];TD.push(tmp);}}}}printf(“%d\n”,result+1);}return 0;}void inTD(){node tmp;for( int i = 0; i < N; i++ ){if( indegree[i] == 0 ){tmp.pos = i;tmp.time = 0;TD.push(tmp);}}return ;}
可以以心感悟，以此沉淀，足矣;耳听佳音，目极美好，
