洛谷P1113 杂务 拓扑排序

题目链接：https://www.luogu.com.cn/problem/P1113

题目让我们求完成所有杂物的最短时间，实际上就是找一条关键路径，这条关键路径上的时间就是答案。找关键路径可以用拓扑排序，当然拓扑排序只适用于有向无环图（DAG）,如果不是有向无环图(DAG)是无法找完所有的点的。
这道题，要记录两个数组，每个节点的开始时间，和结束时间，在拓扑排序的过程中更新，最后遍历结束时间的数组，最大的那个就是答案。
代码如下

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e4+5;
const int maxm=1e6+5;
struct node
{
    int to;
    int next;
}p[maxm];
struct que
{
    int key,value;
};
queue<que>q;
int n,cnt;
int cost[maxn];
int indeg[maxn];
int head[maxn];
int bg[maxn],ed[maxn];//节点开始时间与结束时间
void add(int x,int y)
{
    p[++cnt].next=head[x];
    p[cnt].to=y;
    head[x]=cnt;
}
void topo()//拓扑排序
{
    while(!q.empty())
    {
        que temp=q.front();
        q.pop();
        int u=temp.key,c=temp.value;
        ed[u]=bg[u]+c;
        for(int i=head[u];i;i=p[i].next)
        {
            int v=p[i].to;
            bg[v]=max(bg[v],ed[u]);
            indeg[v]--;
            if(!indeg[v])//入度为0入队
            q.push({v,cost[v]});
        }
    }
}
int main()
{
    scanf("%d",&n);
    int x,y;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&y);
        scanf("%d",&cost[y]);
        while(~scanf("%d",&x)&&x)
        {
            add(x,y);
            indeg[y]++;
        }
        if(!indeg[y])
        q.push({y,cost[y]});
    }
    topo();
    int ans=0;
    for(int i=1;i<=n;i++)
    ans=max(ans,ed[i]);//更新节点最大值为答案
    printf("%dn",ans);
    return 0;
}

最后

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

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