洛谷 1113 杂务 拓扑排序（裸）

题目：
https://www.luogu.org/problem/show?pid=1113

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int MAXN=30001;
int tot,fst[MAXN],nxt[MAXN],dis[MAXN],n,ru[MAXN],lu[MAXN],vis[MAXN];
struct hh
{
    int from,to;
}ma[MAXN<<1];
queue<int>q;
void build(int f,int t)
{
    tot++;
    ma[tot]=(hh){f,t};
    nxt[tot]=fst[f];
    fst[f]=tot;
    return;
}
void bfs()
{
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(int i=fst[x];i;i=nxt[i])
        {
            int v=ma[i].to;
            ru[v]--;
            lu[v]=max(lu[v],lu[x]+dis[v]);
            if(!ru[v]) q.push(v);
        }
    }
    return;
}
void solve()
{
    int x,y,z,ans=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&x,&y);
        dis[x]=y;
        while(~scanf("%d",&y))
        {
            if(y==0) break;
            build(y,x),ru[x]++;
        }
    }
    for(int i=1;i<=n;i++) if(!ru[i]) q.push(i),lu[i]=dis[i];
    bfs();
    for(int i=1;i<=n;i++) ans=max(ans,lu[i]);
    cout<<ans;
}
int main()
{
    solve();
    return 0;
}

最后

以上就是舒服溪流为你收集整理的洛谷 1113 杂务 拓扑排序（裸）的全部内容，希望文章能够帮你解决洛谷 1113 杂务 拓扑排序（裸）所遇到的程序开发问题。

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