【例4-13】奖金（信息学奥赛一本通- P1352）-平芜编程栈

【题目描述】

由于无敌的凡凡在2005年世界英俊帅气男总决选中胜出，Yali Company总经理Mr.Z心情好，决定给每位员工发奖金。公司决定以每个人本年在公司的贡献为标准来计算他们得到奖金的多少。

于是Mr.Z下令召开m方会谈。每位参加会谈的代表提出了自己的意见：“我认为员工a的奖金应该比b高！”Mr.Z决定要找出一种奖金方案，满足各位代表的意见，且同时使得总奖金数最少。每位员工奖金最少为100元。

【输入】

第一行两个整数n,m，表示员工总数和代表数；

以下m行，每行2个整数a,b，表示某个代表认为第a号员工奖金应该比第b号员工高。

【输出】

若无法找到合理方案，则输出“Poor Xed”；否则输出一个数表示最少总奖金。

【输入样例】

2 1 1 2

【输出样例】

【提示】

【数据规模】

80％的数据满足：n≤1000，m≤2000；

100％的数据满足：n≤10000，m≤20000。

1. 题目背景与分析

核心问题：

公司给员工发奖金，存在M条建议，每条建议形式为：“员工A的奖金必须比B高”。要求满足所有建议，且总奖金数最少。基础奖金为 100 元。

模型转化：

这是一个典型的 “依赖关系” 问题。

如果“A的奖金 >B的奖金”，说明B是A的基础（或者说前驱）。只有确定了B的奖金，才能确定A的奖金。

建图方向：建立一条从B指向A的有向边 (B->A)。
图的性质：这是一个有向无环图。如果存在环（例如 A>B, B>A），则无法满足条件，输出 "Poor Xed"。
目标：在满足拓扑序的前提下，求每个节点的最长路径长度（即层级）。

2. 算法选择：Kahn算法+动态规划

为了让总奖金最少，我们采取贪心策略：每个人只拿“刚好满足条件”的最低工资。

即：w[A]=max(所有前驱的工资) + 1。

为什么选择Kahn算法（入度表法）？

天然契合：Kahn 算法的核心是不断剥离“入度为0”的点。在本题中，入度为0 代表“没有比他工资更低的人了”，这些人直接拿基础工资 100 元。
层级递推：随着入度为0的点被移除，它们的后继节点的入度减少。当后继节点入度变为 0 时，说明它的所有下属工资都算好了，此时就可以结算它的工资。
判环简便：算法结束后，如果还有节点的入度不为0，说明存在环，直接判断无解。

3. 数据结构：邻接表（链式前向星）

由于题目数据范围是N<=10000, M<=20000，属于稀疏图。为了时间和空间效率，本题代码使用了邻接表（链式前向星）来存储图。

相比vector，链式前向星在空间上更紧凑，常数更小。

h[u]：存储节点u的第一条边的索引。
vtex[i]：第i条边指向的节点。
nxt[i]：第i条边的下一条同起点边的索引。

4. 完整代码

//Kahn 时间复杂度：O(N+M) 空间复杂度：O(N+M) #include <iostream> #include <queue> using namespace std; int n,m; int h[10010];//邻接表头指针数组 int vtex[20010];//邻接表第i条边终点的下标 int nxt[20010];//与邻接表第i条边同起点的下一条边的索引 int idx; int din[10010];//记录每个点的入度 int w[10010];//记录第i个员工的奖金 long long sum;//记录总奖金 queue<int> q; void addedge(int a,int b){ vtex[idx]=b; nxt[idx]=h[a]; h[a]=idx++; } int main(){ cin>>n>>m; //初始化邻接表头指针数组为-1 for(int i=1;i<=n;i++) h[i]=-1; //邻接表存边 因为本题点数过多，且为稀疏图 不选邻接矩阵 for(int i=1;i<=m;i++){ int a,b; cin>>a>>b; //第a号员工奖金应该比第b号员工高，就建立一条b->a的边 addedge(b,a); din[a]++;//a入度加一 } for(int i=1;i<=n;i++){//遍历所有员工 if(din[i]==0){//如果入度为0 q.push(i);//就入队 //初始化入度为0的员工，奖金100，因为他们不比任何员工奖金高 w[i]=100; } } while(!q.empty()){ int tmp=q.front();//访问队首元素 q.pop();//队首出队 //接下来访问邻接表找到所有与tmp有边相连的员工 int p=h[tmp]; while(p!=-1){ //a为应比tmp奖金高的员工编号 int a=vtex[p]; //更新a员工的奖金 w[a]=max(w[a],w[tmp]+1); //a员工入度-1 din[a]--; //如果a员工入度为0 就入队 if(din[a]==0) q.push(a); //更新指针 p=nxt[p]; } } //结束后，遍历所有员工，如果存在入度不为0的员工 //代表无法找到合理方案 for(int i=1;i<=n;i++){ if(din[i]!=0){ cout<<"Poor Xed"; return 0; } sum+=w[i];//总奖金 } //否则就输出总奖金 cout<<sum; return 0; }

5. 解题总结

建图方向：
- 一定要理清谁依赖谁。本题中“A比B高”意味着 A 依赖 B，所以边是B->A。如果建反了，求出来的就是最小值而不是最大值，逻辑会崩盘。
判环：
- 题目中可能存在矛盾的建议（如 A>B 且 B>A）。Kahn 算法天然支持判环：只要算法结束后还有点没进过队列（即din[i]!=0），就是有环。
数据类型：
- 虽然每个人奖金可能不多，但总奖金sum可能会超过int范围，使用long long是良好的编程习惯。
初始化：
- 链式前向星的h数组记得初始化为-1。
- 入度为0的点，初始奖金设为100。