Top_Sort+Floyd实现关键路径

安昙 · 2018-07-17 09:59:46 · Personal

#include<iostream>
using namespace std;
int n,m;
int g[5000][5000];
int in[5000];
int top[5000];
int d[5000];
void top_sort()
{
    for(int i=1;i<=n;i++)
    {
        int k=1;
        while(k<=n&&in[k]!=0)k++;
        in[k]=0x7fffffff;
        top[i]=k;
        for(int o=1;o<=n;o++)if(g[k][o]!=0)in[o]--;
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b]=c;
        in[b]++;//b的入度++ 
    }
    top_sort();//拓扑排序 
    for(int i=2;i<=n;i++)
        for(int o=1;o<=i-1;o++)
            if(g[top[o]][top[i]]+d[top[o]]>d[top[i]])
                d[top[i]]=g[top[o]][top[i]]+d[top[o]];
    cout<<d[top[n]];
}