洛谷P 1113

题目意思很简单，

把每件事情抽象成点，之后只需要对整个图进行一下拓扑排序，分以下层，之后再用DP 思维，不断地更新每个点最大权值（说白了就是每件事情记录一下最长时间），分层之后跑一边最长路就好了。。

拓扑排序思路：

记录每个点的入度，之后入度为 0 的点处于第一层，之后进行 bfs ，从第一层开始，对于每个点，当被访问到的时候入度减一，当入度为0 代表着我们搜索到了这个点所在的那一层，所以把这个点加入队列。。

思路还是很明了的。。

以下是AC代码

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
inline int read()
{
    int X=0,w=0; char ch=0;
    while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
    while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}
const int maxn = 1e5+5;
struct node
{
    int nxt,to;
}e[maxn];
int head[maxn],tot;
inline void add(int a,int b)
{
    e[++tot].to = b; e[tot].nxt = head[a]; head[a] = tot;
}
int ti[maxn];
int mx[maxn];
int ru[maxn];
int n,ans;
void topo()
{
    queue <int> q;
    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=head[d];~i;i=e[i].nxt)
        {
            int t = e[i].to;
            ru[t]--;
            if(ru[t]==0)
                q.push(t);
            mx[t] = max(mx[t], mx[d]+ti[t]);
        }
    }
    for(int i=1;i<=n;i++)
        ans = max(ans, mx[i]);
}
int main()
{
    n=read();
    memset(head, -1, sizeof head);
    tot = 0;
    for(int i=1;i<=n;i++)
    {
        int a,b,c;
        a=read(),b=read(),c=read();
        ti[a] = b;
        while(c)
        {
            ru[a]++;
            add(c, a);
            c=read();
        }
    }
    topo();
    printf("%d",ans);
    return 0;
}

最后

以上就是坦率小海豚为你收集整理的洛谷P 1113的全部内容，希望文章能够帮你解决洛谷P 1113所遇到的程序开发问题。

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