（POJ 1949）Chores DAG简单DP

本文主要是介绍（POJ 1949）Chores DAG简单DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Chores
Time Limit: 3000MS Memory Limit: 30000K
Total Submissions: 6129 Accepted: 2881
Description

Farmer John’s family pitches in with the chores during milking, doing all the chores as quickly as possible. At FJ’s house, some chores cannot be started until others have been completed, e.g., it is impossible to wash the cows until they are in the stalls.

Farmer John has a list of N (3 <= N <= 10,000) chores that must be completed. Each chore requires an integer time (1 <= length of time <= 100) to complete and there may be other chores that must be completed before this chore is started. We will call these prerequisite chores. At least one chore has no prerequisite: the very first one, number 1. Farmer John’s list of chores is nicely ordered, and chore K (K > 1) can have only chores 1,.K-1 as prerequisites. Write a program that reads a list of chores from 1 to N with associated times and all perquisite chores. Now calculate the shortest time it will take to complete all N chores. Of course, chores that do not depend on each other can be performed simultaneously.
Input

Line 1: One integer, N
Lines 2..N+1: N lines, each with several space-separated integers. Line 2 contains chore 1; line 3 contains chore 2, and so on. Each line contains the length of time to complete the chore, the number of the prerequisites, Pi, (0 <= Pi <= 100), and the Pi prerequisites (range 1..N, of course).
Output

A single line with an integer which is the least amount of time required to perform all the chores.
Sample Input

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
Sample Output

23
Hint

[Here is one task schedule:

    Chore 1 starts at time 0, ends at time 5.Chore 2 starts at time 5, ends at time 6.Chore 3 starts at time 6, ends at time 9.Chore 4 starts at time 5, ends at time 11.Chore 5 starts at time 11, ends at time 12.Chore 6 starts at time 11, ends at time 19.Chore 7 starts at time 19, ends at time 23.

]
Source

USACO 2002 February

题意：
有n个工作要完成，完成每个工作要花一定的时间，而每一个工作可能会有一些前提工作，前提工作没完成就不能做这项工作。多个工作可以同时进行，问你完成所有工作的最少时间为多少？

分析：
读题之后就知道题目是要求关键路径的长度，即最长路的长度。
此时，我们只需要处理好边的权值即可，设w[i]表示完场工作i的时间，所以u->v的权值为w[u],最后d[i]+=w[i]，求最大值即可。
所以我就直接写了spfa()算法，然而超时了。。。。。
由于n<=1e4 所以 m <= n * n <= 1e8,所以会超时。。。。。

由此我们知道，工作v完成的最早时间是他的前驱工作完成的最早时间的最大值+w[v],所以我们就可以直接dp了。
并且，题目的输入是有序的，且保证了前驱工作的编号一定小于当前工作编号，所以可以直接“模拟”一遍即可。

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;const int maxn = 10010;
int dp[maxn],ans;int main()
{int n,u,p,w;while(scanf("%d",&n)!=EOF){ans = 0;for(int i=1;i<=n;i++){scanf("%d%d",&w,&p);int tmp = 0;for(int j=0;j<p;j++){scanf("%d",&u);tmp = max(tmp,dp[u]);}dp[i] = tmp + w;ans = max(ans,dp[i]);}printf("%d\n",ans);}return 0;
}

最长路TLE代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;const int maxn = 10010;
struct edge
{int v,w,next;
}edges[maxn*maxn/2];int n,e;
int head[maxn],d[maxn],w[maxn];
bool vis[maxn];void addedges(int u,int v,int w)
{edges[e].v = v;edges[e].w = w;edges[e].next = head[u];head[u] = e++;
}void spfa()
{queue<int> q;memset(vis,0,sizeof(vis));memset(d,0,sizeof(d));q.push(1);vis[1] = 1;while(!q.empty()){int u = q.front(); q.pop();vis[u] = 0;for(int i=head[u];i!=-1;i=edges[i].next){int v = edges[i].v;int w = edges[i].w;if(d[v] < d[u] + w){d[v] = d[u] + w;if(vis[v] == 0){q.push(v);vis[v] = 1;}}}}
}int main()
{int p,u;while(scanf("%d",&n)!=EOF){e = 0;memset(head,-1,sizeof(head));for(int i=1;i<=n;i++){scanf("%d%d",&w[i],&p);for(int j=0;j<p;j++){scanf("%d",&u);addedges(u,i,w[u]);}}spfa();int ans = 0;for(int i=1;i<=n;i++){ans = max(d[i]+w[i],ans);}printf("%d\n",ans);}return 0;
}