在Linux操作系统中，软件包的安装是有依赖关系的，假设你要安装A软件包，如果A软件包依赖于B软件包，那么你必须先安装B软件包，否则安装A软件包时会出现异常情况，当然也存在一些软件包不依赖于其他软件包便可安装。小强最近要入门Linux系统，于是要安装许多软件包，每个软件包需要花费一定的安装时间，所以这成为一件头疼的事儿。
小强有N个软件要安装分别以一个整数表示1,2,3...N。正如上面所说，这些软件是存在依赖关系的，现在给出这N个软件包的依赖关系(保证不会出现相互依赖的非法情况,即不会出现A依赖于B,B依赖于C，C又依赖于A。)，N个软件包的安装时间，你的任务就是帮助小强算出安装这些软件包至少需要多长时间。
Sample的关系图如下:
- 输入
- 第一行：一个整数N表示有N个软件包需要安装(1 ≤ N ≤ 1000)，接下来的一行有N个整数，第i个整数ti表示i软件包的安装时间(1 ≤ ti ≤ 1000)。
第三行：一个整数M(M ≤ 499,500)表示这N个软件包有M对依赖关系，接下来M行每行分别为两个整数r1 r2表示r1软件包需要在r2软件包安装完成后才可以安装(1 <= r1, r2 <= N)。 - 输出
- 一个整数t表示至少需要t时间才可以完成所有软件包的安装。
- 样例输入
-
3 2 3 1 2 1 2 1 3
- 样例输出
-
5
-
提示
系统支持同时安装多个软件包。
解法：
比如R1的安装时依赖R2和R3的，那么在安装R1之前就必须看安装R2和R3那个花的时间更长，然后取更长的那个时间作为R1的安装开始时间，然后一直深搜下去
注意：程序中用到了STL的vector容器；dp[i]数组是用来记录i安装完后此时所需的时间，相当于记录中间值，初始时肯定都是0；
AC CODE
#include<iostream> #include<string.h> #include<vector> #include<stdio.h> #define N 1010 using namespace std; vector<int>ivec[N]; int dp[N]; int t[N]; int dfs(int u) { int i; int tx,max; tx=max=0; for(i=0;i<ivec[u].size();i++) { if(dp[ivec[u][i]]!=0)tx=dp[ivec[u][i]];/*前面已经记录了完成ivec[u][i]所需的时间，故没有必要重新计算一遍*/ else tx=dfs(ivec[u][i]); if(max<tx)max=tx; } dp[u]=max+t[u]; return max+t[u]; } int main() { int n,m; int u,v; int i; int tx; int max; while(scanf("%d",&n)!=-1) { memset(dp,0,sizeof(dp)); memset(t,0,sizeof(t)); for(i=1;i<=n;i++) scanf("%d",&t[i]); scanf("%d",&m); while(m--) { scanf("%d%d",&u,&v); ivec[u].push_back(v); } max=0; for(i=1;i<=n;i++) { if(dp[i]==0) tx=dfs(i); if(tx>max)max=tx; } printf("%d\n",max); } return 0; }