hdu 4109 Instrction Arrangement 拓扑排序 关键路径

这个算是关键路径的模版题目了，解这个题目之前，首先说下关键路径的含义，传送门（度娘），个人的见解是，关键路径就是木桶的短板问题，比如有一群人约好去某个地方，大家从同一个地方同一时间开始出发，有些人选择骑车，有些人选择走路，有些选择公交。。。。。。那么最迟到达的那个人需要的时间就相当于关键路径。

图可能不是连通的，但这个不影响，我们只需要计算最长的那段

以下是代码，相当于在拓扑排序下求各个点到起点的最长路径

#include<stdio.h> #include<string.h> #include<stdlib.h> #define val 1001 struct link {int v;int cost;struct link *next; }; struct node {struct link *next; }vode[val]; int into[val],ee[val],n,m;//into表示入度，ee表示从最早完成该任务的时间，ee初始化为1 void topsort();//拓扑排序，边拓扑边求最长路径 void create_link(); int main() {int i,j,ans;while(scanf("%d %d",&n,&m)!=EOF){memset(into,0,sizeof(into));for(i=0;i<n;i++)ee[i]=1;create_link();ans=0;topsort();for(i=0;i<n;i++)if(ee[i]>ans) ans=ee[i];printf("%d\n",ans);}return 0; } void create_link() {int i,j,a,b,c;struct link *s;for(i=0;i<n;i++)vode[i].next=NULL;for(i=0;i<m;i++){scanf("%d %d %d",&a,&b,&c);into[b]++;s=(struct link*)malloc(sizeof(struct link));s->v=b;s->cost=c;s->next=vode[a].next;vode[a].next=s;} } void topsort() {int i,j,v;struct link *p;for(i=0;i<n;i++){for(j=0;j<n;j++)if(into[j]==0) {v=j;break;}into[v]=-1;p=vode[v].next;while(p!=NULL){if(ee[p->v]<ee[v]+p->cost)//如果权值和更大，则替换ee[p->v]=ee[v]+p->cost;into[p->v]--;p=p->next;}} }

转载于:https://www.cnblogs.com/yobobobo/archive/2012/08/06/3826866.html

总结

以上是生活随笔为你收集整理的hdu 4109 Instrction Arrangement 拓扑排序 关键路径的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。