题目

算法设计题三：基于图论的奖金分配问题
由于无敌的凡凡在2005年世界英俊帅气男总决选中胜出,Yali Company总经理Mr.Z心情好,决定给每位员工发奖金.公司决定以每个人本年在公司的贡献为标准来计算他们得到奖金的多少.
于是Mr.Z下令召开m方会谈.每位参加会谈的代表提出了自己的意见：“我认为员工a的奖金应该比b高!”Mr.Z决定要找出一种奖金方案,满足各位代表的意见,且同时使得总奖金数最少.每位员工奖金最少为100元.
【输入】
第一行两个整数n,m,表示员工总数和代表数；
以下m行,每行2个整数a,b,表示某个代表认为第a号员工奖金应该比第b号员工高.
【输出】
若无法找到合法方案,则输出“Poor Xed”；否则输出一个数表示最少总奖金.

提问时间：2021-01-19

答案

按M个代表的意见建图,若图中有环则无解,否则拓扑排序之后算出总奖金.