家庭琐事问题

一 原问题链接

Chores - POJ 1949 - Virtual Judgehttps://vjudge.net/problem/POJ-1949

二 输入与输出

1 输入

第1行包含一个整数 N。第 2 ~ N+1 行描述每个家务，第 2 行包含家务1；第 3 行包含家务2，以此类推。每行都包含完成家务的时间、先决条件的数量 Pi 和 Pi 个先决条件。

2 输出

单行输出完成所有家务所需的最少时间。

三  输入与输出样例

1 输入

7

5 0

1 1 1

3 1 2

6 1 1

1 2 2 4

8 2 2 4

4 3 3 5 6

2 输出

23

四 分析和设计

1 拓扑图

 2 分析

家务 1 在时间0开始，在时间 5 结束；

家务 2 在时间0开始，在时间 6 结束；

家务 3 在时间0开始，在时间 9 结束；

家务 4 在时间0开始，在时间 11 结束；

家务 5 在时间0开始，在时间 12 结束；

家务 6 在时间0开始，在时间 19 结束；

家务 7 在时间0开始，在时间 23 结束；

本问题的关键在于，家务 k 只能以家务 1~k-1 作为先决条件。也就是说，输入第 K 个家务时，它的先决条件均已确定什么时间结束。因此在输入过程中直接求最长距离即可。如果没有先决条件的限制，则不可以这样计算。

五 代码

package graph.poj1949;

import java.util.Scanner;

public class POJ1949 {
    static final int maxn = 10010;
    static int d[] = new int[maxn];
    static int n;

    public static void main(String[] args) {
        int ans = 0, w, num, y;
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();

        for (int i = 1; i <= n; i++) {
            w = scanner.nextInt();
            num = scanner.nextInt();
            d[i] = w;
            for (int j = 1; j <= num; j++) {
                y = scanner.nextInt();
                d[i] = Math.max(d[i], d[y] + w);
            }
            ans = Math.max(ans, d[i]);
        }
        System.out.println(ans);
    }
}

六 测试

绿色为输入，白色为输出