这道题一开始出现在我们训练的专题中是打算放弃的，因为学长说这道题要用到“拓扑排序”，对于这个拓扑排序我一无所知，后来学习了学长的代码加上网查了点资料就有点了解了。 先来说说这道题 题意 ： 一位大老板要为他的员工发工资，但是这些员工有攀比心，即某个人要求他的工资比某个人高，但他们的老板是个好老板，他决定满足所有人的要求，并且最小工资是 888 。那么我们当然就能想到，在这个环境之下，老板支付最少的情况就是同一阶级的人们都发一样的工资并且从888开始，以后每一阶级只增加一块钱！ 输入 ： 第一行 两个数 n m ,表示有n位员工，有m条要求，接下来m行 每行 输入a b,表示 a的工资要比b高 做法： 那么我的做法是，用拓扑排序。拓扑排序就是指在一个“有向图”中每个点只会出现一次，并且那些点有出度和入度（例如 a -> b 那么a就是b的入度，b就是a的出度）那么按照题目输入把图画出来后，我们能找到一个点，它的出度为0，也就是说他没有指向的目标，根据题意也就是它是最低级要求，那么就把这个点放进队列里面。找到所有出度为0的点放进队列里。然后就循环你的队列，在里面从上面开始把里面的点拿出来，（ps：拓扑排序所用到的一个函数vector，它生成一个动态数组，在这个点的结构体里面，用来存这个点的上家，也就是这个点的入度）然后把这个点的工资算上后，把它的入度点的出度都减一，然后减过后如果出现了出度为0的点，也把它放进队列里，这样进行到底就可以了，那么如果这个图出现了环（就是 a -> b,b ->c,c->a）那么这种情况是无解的，输出-1 代码：
#include<bits/stdc++.h> using namespace std; #define maxn 40010 struct node{ vector <int> child; //生成动态数组用来储存 一个点的上家 int du,n; }num[maxn]; queue<node>q; //创建一个队列 int main(){ int n,m,a,b,ans,total; while(scanf("%d %d",&n,&m) != EOF){ while(!q.empty()) //清空队列 q.pop(); memset(num,0,sizeof(num)); for(int i = 0;i < m;i++){ scanf("%d %d",&a,&b); num[b].child.push_back(a); //把 a 作为 b 的上家 num[a].du++; // 从 a 到 b 所以 a 出度加一 } for(int i = 1;i <= n;i++){ if(num[i].du == 0){ //出度为 0的点就可以放进队列了，因为此时它是最低级 num[i].n = 0; q.push(num[i]); //把这个出度为 0 的放进队列进行操作 } } ans = total = 0; while(!q.empty()){ node p = q.front(); q.pop(); ans += p.n; // n用来表示这个点是第几批进队列的点 total++; //total 表示已经处理过的点的个数 for(int i = 0;i < p.child.size();i++){ // p.child.size()表示 该数组里的元素个数 num[p.child[i]].du--; // 处理这个点的时候，这个点的所有上家的出度要减一 if(num[p.child[i]].du == 0){ //处理完后如果这个点的出度为 0，那么它也可以放进队列进行操作了 num[p.child[i]].n = p.n + 1; // 下一批进队列的要比上一批出队列的等级高，所以 n + 1 q.push(num[p.child[i]]); // 把要操作的点放进队列 } } } ans += n * 888; //因为题目说工资最少是888，所以除了已经加进去的多的工资，每个人都要把最小工资加上 if(total != n) // 如果total ！= n 表示里面成环了，不会出现出度为 0 的点了，无解 ans = -1; printf("%d\n",ans); } }