大气的网络公司名字/seo网络营销招聘

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

基本思路：

1. 采取入度表示：一个元素有多少个前序元素，即有多少组序列对 并且该元素在序列对后边部分
2. 每次找到一个入度为0的元素加入到结果中，同时，将所有其后续元素的入度-1
3. 重复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城市的后序城市 入度-1for(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;}