题目描述：
????????在一个任务调度系统中，需要调度执行一系列的任务，任务之间存在依赖关系，
如任务A依赖任务B，则任务A必须在任务B完成后才能开始启动执行现在给出n个任务的依赖关系与执行时间，n <= 10000，请计算这n个任务执行完成所需要的时间（假设计算资源充足，允许任意多的任务并行执行），如果任务存在循环依赖则输出-1
输入描述：
????????第一行输入任务个数n，正整数数字
????????第二行开始为n个任务的信息，任务信息分为两部分，第一部分是所依赖的任务ID(整形，索引顺序，从0开始)，第二部分为计算所需时间（正整数）。两部分以空格分隔。任务可能依赖多个其他任务，多个任务ID之间以半角都好','分隔，如果任务不依赖其他任何任务，则依赖ID输入-1
????????如：
?? ??? ?输入：
? ? ? ? ? ? 3
? ? ? ? ? ? -1 1
? ? ? ? ? ? -1 2
? ? ? ? ? ? -1 3
输出描述：
????????输出所有任务执行完成所需要的时间，如果人物之间存在循环依赖则输出-1
????????如：
????????输出：
? ? ? ? ? ? ?3
说明：
? ? ? ? 这是0825的华为机试第三题，博主是近期整理的，所以不知道会AC多少，只是测试用例过了，也选择了几个其他用例作为测试，仅供参考。
? ? ? ? 使用的方法是：有向无环图排序|构造入度表|DFS
解题思路：
? ? ? ? 记录每个任务所依赖的任务，根据每个依赖关系画出任务之间的有向无环图，从入度为0的任务出发，深度遍历统计所需要的最短时间
?具体方法：
? ? ? ? 1、统计每个任务的依赖关系，利用vector容器，使用vector下标作为任务ID的天然索引，对于每个任务依赖的任务同样使用vector容器统计，其中涉及到要对字符串输入分割（任务之间使用，隔开）；
? ? ? ? 2、根据每个任务的依赖任务，统计出每个任务的入度；
? ? ? ? 3、从入度为0的任务出发，深度遍历有向无环图，记录任务执行的时间；
代码如下：? ? ? ??
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int maxTime = 0;
void dfs(vector<vector<int>>& graph, vector<int> time, int task, int cost) {
if (task == -1) {
//到没有依赖的任务
maxTime = max(maxTime, cost);
return;
}
vector<int> depends = graph[task];
for (int depend:depends) {
dfs(graph, time, depend, cost + time[task]);
}
}
int completeTime(vector<vector<int>>& graph, vector<int> time) {
//统计入度
vector<int> indegree(time.size(), 0);
for (vector<int> g : graph) {
for (int i = 0; i < g.size(); ++i) {
if (g[i] == -1) continue;
++indegree[g[i]];
}
}
vector<int> path;
for (int i = 0; i < indegree.size(); ++i) {
if (indegree[i] == 0) path.push_back(i);
}
if (path.size() == 0) return -1;
int tmpTime = 0;
for (int task : path) {
dfs(graph, time, task, 0);
}
return maxTime;
}
vector<int> split(string& s, char symbol) {
vector<int> res;
int n = s.size();
int idx;
int left = 0;
string tmp;
while (s.find(symbol, left) != s.npos) {
idx = s.find(symbol, left);
tmp = s.substr(left, idx-left);
left = idx + 1;
res.push_back(atoi(tmp.c_str()));
}
tmp = s.substr(left, s.size() - left);
res.push_back(atoi(tmp.c_str()));
return res;
}
int main() {
int n;
cin >> n;
vector<vector<int>> depend(n);
vector<int> time(n);
string tmp;
for (int i = 0; i < n; ++i) {
cin >> tmp >> time[i];
depend[i] = split(tmp, ',');
}
cout << completeTime(depend, time) << endl;
}