阿里测试

今天我们看到的阿里巴巴提供的任何一项服务后边都有着无数子系统和组件的支撑，子系统之间也互相依赖关联，

其中任意一个环节出现问题都可能对上游链路产生影响。小明做为新人接收到的第一个任务就是去梳理所有的依赖关系，

小明和每个系统的负责人确认了依赖关系，记录下调用对应系统的耗时，用这些数据分析端到端链路的数目和链路上最长的耗时。

输入： 小明搜集到的系统耗时和依赖列表

5  4   // 表示有5个系统和 4个依赖关系

3      // 调用1号系统耗时 3 ms

2      // 调用2号系统耗时 2 ms

10     // 调用3号系统耗时 10 ms

5      // 调用4号系统耗时 5 ms

7      //  调用5号系统耗时 7 ms

1 2    //  2号系统依赖1号系统

1 3    //  3号系统依赖1号系统

2 5    //  2号系统依赖5号系统

4 5    //  4号系统依赖5号系统

输出:  调用链路的数目 和最大的耗时， 这里有三条链路1->2->5，1->3， 4->5，最大的耗时是1到3的链路 3+10 = 13，无需考虑环形依赖的存在。

3  13

解题：有map来保存连接的关系，有vector<vector<int>>保存连接的路径，依次递归寻找父节点的儿子节点

#include <map>
#include <iostream>
#include <vector>

using namespace std;

void find_Path(multimap<int, int> &Relev, vector<double> &timeUsed,
	vector<int>& path, vector<vector<int> > &paths, int key, int &time, int &maxTime) {

	multimap<int, int>::iterator iter;
	time += timeUsed[key];
	path.push_back(key);

	if ((iter = Relev.find(key)) != Relev.end())
	{
		int n = Relev.count(key);
		for (int j = 0; j < n; ++j, ++iter) 
		{
			find_Path(Relev, timeUsed, path, paths, iter->second, time, maxTime);
		}
	}
	else 
	{
		paths.push_back(path);
		if (maxTime < time)
			maxTime = time;
	}

	time -= timeUsed[key];
	path.pop_back();
}
int main()
{
	int m, n;
	cin >> m >> n;
	vector<double> timeUsed(m + 1);
	bool* isHead = new bool[m + 1];
    memset(isHead, 1, m + 1);
	multimap<int, int> mp;
	int maxTime = 0;
	vector<vector<int> > paths;
	for (int i = 1; i <= m; ++i)
	{
		double time;
		cin >> time;
		timeUsed[i] = time;
	}
	for (int i = 0; i < n; ++i) 
	{
		int Master, Slave;
		cin >> Master >> Slave;
		mp.insert(make_pair(Master, Slave));
		isHead[Slave] = false;
	}

	for (int i = 1; i <= m; ++i) 
	{
		if (isHead[i]) 
		{
			int time = 0;
			vector<int>path;
			find_Path(mp, timeUsed, path, paths, i, time, maxTime);
		}
	}

	delete[] isHead;
	cout << paths.size() << " " << maxTime << endl;
	return 0;
}