1352：【例4-13】奖金
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
由于无敌的凡凡在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
【输出样例】
201
【提示】
【数据规模】
80％的数据满足：n≤1000，m≤2000；
100％的数据满足：n≤10000，m≤20000。
1. //示例代码 拓扑排序 2. #include<iostream> 3. using namespace std; 4. 5. int a[10001][301] = { 0 }; // 邻接表，用于存储图的信息 6. int into[10001]; // 计算每个结点的入度 7. int ans[10001]; // 记录拓扑排序的结果 8. int m, n; // n：图的结点数量，m：图的边数 9. int money; // 统计 Xed 赚取的钱 10. 11. void init() // 初始化图 12. { 13. int i, x, y; 14. cin >> n >> m; 15. for (i = 1; i <= m; i++) 16. { 17. cin >> x >> y; 18. a[y][0]++; // 将 y 的出度加一 19. a[y][a[y][0]] = x; // 将有向边(x,y)加入邻接表中 20. into[x]++; // 将 x 的入度加一 21. } 22. } 23. 24. bool topsort() // 拓扑排序 25. { 26. int t, tot, k, i, j; 27. tot = 0; k = 0; 28. while (tot < n) // 进行拓扑排序，将排序结果记录在数组 ans 中 29. { 30. t = 0; // t: 当前可以被访问的入度为 0 的结点数量 31. for (i = 1; i <= n; i++) 32. { 33. if (into[i] == 0) 34. { 35. tot++; t++; money += 100; // 访问一个结点需要花费 100 元 36. ans[t] = i; // 记录拓扑排序的结果 37. into[i] = 0xfffffff; // 将入度设置为一个非常大的数，代表该结点已经被访问过 38. } 39. } 40. if (t == 0) return false; // 如果没有入度为 0 的结点，则说明图中存在环，返回 false 41. money += k * t; k++; // 根据 Xed 的规则计算赚取的钱 42. for (i = 1; i <= t; i++) 43. for (j = 1; j <= a[ans[i]][0]; j++) into[a[ans[i]][j]]--; // 更新拓扑排序中各个结点的入度 44. } 45. return true; 46. } 47. 48. int main() 49. { 50. init(); money = 0; 51. if (topsort()) cout << money << endl; // 进行拓扑排序并输出 Xed 赚取的钱 52. else cout << "Poor Xed" << endl; 53. return 0; 54. }
