Leetcode 旅行1：拓扑排序+小根堆

拓扑排序是解决这样一类问题，问题包含N个元素，存在若干组序列对（A,B），要求序列对中A一定要排在B前面。给出一个排序序列使得满足所有要求。

基本思路：

采取入度表示：一个元素有多少个前序元素，即有多少组序列对 并且该元素在序列对后边部分每次找到一个入度为0的元素加入到结果中，同时，将所有其后续元素的入度-1重复2 直到所有元素都加入到结果中。

题意：

准备去N个城市旅行，去每个城市的开销是Ai​元。在去y城市之前先旅游x城市，列出了这些限制条件list。只有V元，每次会选择当前能去的花费最小的城市,如有多个花费一样的则首先去编号小的城市，最多能到多少个城市去旅游。

输入：

给定N, V，A数组，List数组

其中A[i]表示第i个城市花费  List中 point.x point y表示一组前后顺序城市对

输出：

一行一个数字表示输出牛妹能去的最多城市数目

示例1

输入

复制

3,10,[3,7,8],[(1,2)]

输出

复制

2

说明

先去1号城市再去2号城市，花费为 3+7=10

 

 

思路：

将所有入度为0的城市加入一个小根堆，堆顶元素即为花费最少，并且序号最小的城市。每次取堆顶城市加入，同时花费V-cost  。若V<0  那么break   同时将该城市的所有后序城市入度-1  若后序城市入度减一之后为0   那么这个后序城市加入到小根堆中结束的条件为 花费V<0  或者小根堆为空（遍历完所有城市）

 

struct city { int id; int cost; city(int _id,int _cost) { id=_id; cost=_cost; } }; //priority_queue 小根堆比较器： 仿函数 重载 operator() 方法 class cmp { public: bool operator()(city& a,city& b) { if(a.cost==b.cost) return a.id>b.id; return a.cost>b.cost; } }; int Travel(int N, int V, int* A, int ALen, vector<Point>& list) { map<int,vector<int>> mp;//存放每个城市 到 下一城市群 的映射 vector<int> count(ALen,0);//存放每个城市的前序城市计数 for(int i=0;i<list.size();i++) { int x=list[i].x-1; int y=list[i].y-1; count[y]++; if(mp.find(x)==mp.end()) mp[x]=vector<int>(); mp[x].push_back(y); } priority_queue<city,vector<city>,cmp> q;//优先队列存放那些 可以直接去的城市（没有前序城市） for(int i=0;i<ALen;i++) { if(count[i]==0) //可以直接去 q.push(city(i,A[i])); } int ans=0; int sum=0; while(sum<=V && q.empty()==false) { city temp=q.top();//取最小开销的那个城市 q.pop(); sum+=temp.cost; ans++; if(sum>V) { ans--; break; } //同时将temp城市的后序城市 入度-1 for(int i=0;i<mp[temp.id].size();i++) { count[mp[temp.id][i]]--; if(count[mp[temp.id][i]]==0) //若后续城市入度减完以后 变为0 那么加入小根堆中 { q.push(city(mp[temp.id][i],A[mp[temp.id][i]])); } } } return ans; }