洛谷 P1113 杂务 拓扑排序

题目链接：https://www.luogu.org/problemnew/show/P1113

思路：

1：拓扑排序

2：每一个节点的最早完成时间等于其前驱结点中最晚的那一个的完成时间加上该节点本身的完成时间

mx[i]=max(mx[i],mx[d]+ti[i]);

3：整个工程的最早完成时间就等于所有结点中，最后完成的那一个结点的最早完成时间

for(int i=1;i<=n;i++)
        ans=max(ans,mx[i]);

#include <iostream>
#include <queue>
#include<algorithm>
#include<cstdio>

using namespace std;
const int N=10005;
queue<int>q;
bool e[N][N];
int ti[N];
int mx[N];
int ru[N];
int n,ans;
void tuop()
{
    for(int i=1;i<=n;i++)
    {
        if(ru[i]==0)
        {
            q.push(i);
            mx[i]=ti[i];
        }
    }
    while(!q.empty())
    {
        int d=q.front();
        q.pop();
        for(int i=1;i<=n;i++)
        {
            if(e[d][i])
            {
                ru[i]--;
                if(ru[i]==0)
                {
                    q.push(i);
                }
                mx[i]=max(mx[i],mx[d]+ti[i]);
            }
        }
    }
    for(int i=1;i<=n;i++)
        ans=max(ans,mx[i]);
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        ti[a]=b;
        while(c!=0)
        {
            ru[a]++;
            e[c][a]=true;
            cin>>c;
        }
    }
    tuop();
    cout<<ans<<endl;
    return 0;
}

思路参考博客：题解区https://www.luogu.org/blog/amstar/solution-p1113

最后

以上就是想人陪人生为你收集整理的洛谷 P1113 杂务 拓扑排序的全部内容，希望文章能够帮你解决洛谷 P1113 杂务 拓扑排序所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。