P1113 杂务

63 阅读 0 评论 42 点赞

我是靠谱客的博主飘逸睫毛膏，最近开发中收集的这篇文章主要介绍P1113 杂务，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

分析:可以把每个任务看成都一个节点,如果有2个任务a,b,如果a是b的准备工作,那么就在a,b之间连一条有向边。由于互相没有关系的杂务可以同时工作,所以发现所有杂务都被完成的最短时间取决与最晚被完成的那个任务，于是需要找到最晚被完成任务的时间。

因为题目中有一个性质:"杂务k(k>1)的准备工作只可能在杂务1至k-1中。",所以这个图是无环的，且题目中的边是有方向的，于是这道题就是一个有向无环图(DAG)

这样,问题就变成了:给定一个DAG,求它的一个最长链。

可以用一个dp的思想来做,对每个任务用zx数组记录完成这个任务所需的最短时间，由于每个任务必须在所有准备工作完成后才能完成，所以完成每个任务所需的最短时间就是所有准备任务中最晚完成的时间+这个任务需要完成的时间，也就是每个节点中zx的取值。

代码:

#include <bits/stdc++.h>
using namespace std;
int n,ans,x,len[22222],zx[22222];
vector<int>a[10001];//a[该任务的编号][该任务的所有前置任务的编号]
int f(int p)
{
  if(zx[p]) return zx[p];//如果这个节点被访问过,直接返回这个节点的最短路径 
  int u = 0;
  for(int i = 0; i < a[p].size(); i++) u = max(f(a[p][i]),u);//找到所有连向此节点的点中时间最长的一个 
  zx[p] = u + len[p];//加上完成此节点的时间 
  return zx[p]; 
}
int main()
{
  cin>>n;
  for(int i = 1; i <= n; i++)
  {
    cin>>x>>len[i];
    int t;
    while(cin>>t)
    {
      if(t == 0) break;
      a[t].push_back(x);
    }
  }
  for(int i = 1; i <= n; i++) ans = max(ans,f(i));
  cout<<ans;
  return 0;
}