题解 P1113 【杂务】

Manjusaka丶梦寒 · 2018-07-15 19:50:30 · 题解

翻了翻题解发现都是什么拓扑？最长路？dfs？哦！！我天，dalao dalao。

不过楼下dalao的代码长度着实让我折服。

为什么要做的那么麻烦。

在这说一下我的解法，既然第k件事的准备一定在第1到k-1件事中，那么不难想到二者之间的联系。 那么开始循环处理每一件事的结束时间，比较取max不就好了，具体理解看代码。

/*....................
作者：Manjusaka
时间：2018/7/5
题目：luogu P1113 杂务  
......................*/

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
int n,ans;
struct ahah
{
    int need,over;        // need 表示需要时间 ，over表示结束时间。 
    int pre[111],tot;    // pre[],tot 表示开始这件事前有tot件事要准备，pre储存。 
} edge[10010];
int main()
{
    int x,y,z;
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d%d",&x,&edge[i].need);
        while(scanf("%d",&y)==1&&y!=0)edge[x].pre[++edge[x].tot]=y;
    }
    edge[1].over=edge[1].need;
    for(int i=2; i<=n; i++)
    {
        for(int j=1; j<=edge[i].tot; j++)
        {
            edge[i].over=max(edge[i].over,edge[edge[i].pre[j]].over+edge[i].need);
        //可能比较混乱，这件事的结束时间一定是这些事完成后再做，
        //所以取每件事完成的时间加上现在这件事的时间 ,作为目前所处理到的时间的完成时间。 
        }
        ans=max(ans,edge[i].over);
    }
    printf("%d",ans);
}