Luogu P1113 杂务Luogu P1113 杂务

Luogu P1113 杂务

我真的不知道为什么这题是图论题……
因为第(n)件事的前驱只会在前(n-1)件事中，所以可以从第(1)件事开始遍历。
而且，最优的情况便是第(i)件事的结束时间尽量大（第(1)件事的结束时间就是第(1)件事的花费时间），就选择第(i)件事作为第(n)件事的前驱。
得到每件事的结束时间后，与(ans)取max即可。（注意这题是让我们求时间的最小值，但要用max取答案，思维容易走进误区）

#include<bits/stdc++.h>
#define N 50010

using namespace std;

int n,ans;

struct node {
    int time,finish,cnt;
    int pre[110];
}event[N];

void Read() {
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        int id,preevent;
        scanf("%d%d",&id,&event[i].time);
        while(scanf("%d",&preevent)&&preevent!=0) {
            event[i].pre[++event[i].cnt]=preevent;
        }
    }
    return;
}

void Solve() {
    event[1].finish=event[1].time;
    for(int i=2;i<=n;i++) {
        for(int j=1;j<=event[i].cnt;j++) {
            event[i].finish=max(event[i].finish,event[event[i].pre[j]].finish+event[i].time);
        }
        ans=max(ans,event[i].finish);
    }
    printf("%d",ans);
    return;
}

int main()
{
    Read();
    Solve();
    return 0;
}