這個算是關鍵路徑的模版題目了，解這個題目之前，首先說下關鍵路徑的含義，傳送門（度娘），個人的見解是，關鍵路徑就是木桶的短板問題，比如有一群人約好去某個地方，大家從同一個地方同一時間開始出發(fā)，有些人選擇騎車，有些人選擇走路，有些選擇公交。。。。。。那么最遲到達的那個人需要的時間就相當于關鍵路徑。

圖可能不是連通的，但這個不影響，我們只需要計算最長的那段

以下是代碼，相當于在拓撲排序下求各個點到起點的最長路徑

#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 拓扑排序 关键路径的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。