POJ1949---家务琐事

题目描述

Farmer John 的家人在挤奶时会帮忙做家务，尽可能快地完成所有家务。在 FJ 家，有些家务要等到其他家务完成后才能开始，例如，在牛栏上之前是不可能洗牛的。

Farmer John 列出了必须完成的 N (3 <= N <= 10,000) 个家务。每个杂务需要一个整数时间（1 <= 时间长度 <= 100）来完成，并且可能还有其他杂务必须在此杂务开始之前完成。我们将这些先决条件称为杂务。至少有一项家务活没有先决条件：第一个，编号 1。Farmer John 的家务活列表很好地排序，家务 K (K > 1) 只能有家务 1,.K-1 作为先决条件。编写一个程序，读取从 1 到 N 的杂务列表以及相关的时间和所有额外的杂务。现在计算完成所有 N 个家务所需的最短时间。当然，互不依赖的杂务可以同时进行。

输入

第 1 行：一个整数，N

Lines 2…N+1: N 行，每行有几个空格分隔的整数。第 2 行包含杂务 1；第 3 行包含杂务 2，依此类推。每行包含完成家务的时间长度、先决条件的数量 Pi (0 <= Pi <= 100) 和 Pi 先决条件（范围 1…N，当然）。

输出

一行带有一个整数，它是执行所有家务所需的最少时间。

输入样例

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

输出样例

23

思路:这个题也就是求关键路径的长度,但这个题比较特殊.对于每个事件的时间是放在节点上的.另外每个事件的前驱事件都比该事件号小.所有事件的输入都是按照顺序从前往后输入的.

所有当程序执行到事件u,那么u的前驱的事件的dis都已经更新到了最大值.这样可以直接进行寻找u的最长路径.==>前驱已经给出,一个个进行判断更新即可.

注:一般情况下,求关键路径的长度(也就是最长路径的长度)时,有以下思路

利用Bellman-Ford改变松弛条件,求最长路.

利用SPFA改变松弛条件,求最长路.

利用拓扑序列+松弛条件,来求解最长路.

参考代码

#include<iostream>
using namespace std;
const int maxn = 10000+10;
int n,dis[maxn],t,num,v,ans;
int main()
{
  cin>>n;
  for(int u = 1; u <=n ;u++){
    cin>>t>>num;
    dis[u] = t;//先进行该节点的dis更新 ,对于第一个节点,没有前驱节点,如果不进行更新,那么值就不符合实际意义. 
    for(int j = 1;j <= num; j++){
      cin>>v;
      if(dis[u] < dis[v]+t){
        dis[u] = dis[v]+t;
      }
    } 
    if(ans<dis[u]){//更新最长路径 
      ans = dis[u];
    }
  }
  cout<<ans<<endl; 
  return 0;
}