poj 1949 Chores (拓扑排序+dp)

tags:

  • codeforces
  • 算法竞赛
  • dp
  • acm
  • ACM

http://poj.org/problem?id=1949

题意:

有n个任务,第i个任务需要时间xi来完成,并且第i个任务必须在它 “前面的” 某些任务完成之后才能开始。

给你任务信息,问你最短需要多少时间来完成任务。

思路:

拓扑排序+dp

拓扑排序的过程中做个dp,可以保证dp的顺序…

对于这道题,找出每条依赖链,然后做dp即可。

  1/* ***********************************************
  2Author :111qqz
  3Created Time :2017年11月07日 星期二 13时52分27秒
  4File Name :3249.cpp
  5************************************************ */
  6
  7#include <iostream>
  8#include <cmath>
  9#include <queue>
 10#include <cstdio>
 11#include <cstring>
 12#define PB push_back
 13#define fst first
 14#define sec second
 15#define lson l,m,rt<<1
 16#define rson m+1,r,rt<<1|1
 17#define ms(a,x) memset(a,x,sizeof(a))
 18typedef long long LL;
 19#define pi pair < int ,int >
 20#define MP make_pair
 21
 22using namespace std;
 23const double eps = 1E-8;
 24const int dx4[4]={1,0,0,-1};
 25const int dy4[4]={0,-1,1,0};
 26const int inf = 0x3f3f3f3f;
 27const int N=1E5+7;
 28vector <int>edge[N];
 29int in[N],out[N];
 30int n;
 31int dp[N];
 32int val[N];
 33void init()
 34{
 35    for ( int i = 0 ; i < N ; i++) edge[i].clear();
 36    ms(in,0);
 37    ms(out,0);
 38    ms(dp,0xca);
 39 //   cout<<"dp:"<<dp[1]<<endl;
 40}
 41void topo()
 42{
 43    queue<int>Q;
 44    for ( int i = 1 ; i <= n ; i++)
 45    if (in[i]==0) Q.push(i),dp[i] = val[i];
 46
 47    while (!Q.empty())
 48    {
 49    int cur = Q.front();
 50//  cout<<"cur:"<<cur<<endl;
 51    Q.pop();
 52    int siz = edge[cur].size();
 53    for ( int i = 0 ; i < siz ; i++)
 54    {
 55        int v = edge[cur][i];
 56//      printf("%d->%d val[v]:%d dp[cur]: %d dp[v]:%d ",cur,v,val[v],dp[cur],dp[v]);
 57        dp[v] = max(dp[v],dp[cur]+val[v]);
 58//      printf("new dp[v]:%d\n",dp[v]);
 59        in[v]--;
 60        if (in[v]==0) Q.push(v);
 61    }
 62    }
 63}
 64void pr()
 65{
 66    for ( int i = 1 ; i <= n ; i++) printf("%d%c",dp[i],i==n?'\n':' ');
 67}
 68int main()
 69{
 70#ifndef  ONLINE_JUDGE 
 71    freopen("./in.txt","r",stdin);
 72#endif
 73    while (~scanf("%d",&n))
 74    {
 75    init();
 76    for ( int i = 1 ; i <= n ; i++)
 77    {
 78        int x,m;
 79        x = i;
 80        scanf("%d %d",&val[i],&m);
 81        while (m--)
 82        {
 83        int y;
 84        scanf("%d",&y);
 85        //      cout<<"x:"<<x<<" y:"<<y<<endl;
 86        edge[y].PB(x);
 87        out[y]++;
 88        in[x]++;
 89        }
 90    }
 91    topo();
 92    int ans = -inf;
 93//  pr();
 94    for ( int i = 1 ; i <= n ; i++) if (!out[i]&&dp[i]>ans) ans = dp[i];
 95    printf("%d\n",ans);
 96    }
 97
 98
 99
100#ifndef ONLINE_JUDGE  
101    fclose(stdin);
102#endif
103    return 0;
104    }