1498: 奖金
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：34
解决：2
题目描述
由于无敌的凡凡在2005年世界英俊帅气男总决选中胜出，Yali Company总经理Mr.Z心情好，决定给每位员工发奖金。公司决定以每个人本年在公司的贡献为标准来计算他们得到奖金的多少。
于是Mr.Z下令召开方会谈。每位参加会谈的代表提出了自己的意见：“我认为员工a的奖金应该比b高！”Mr.Z决定要找出一种奖金方案，满足各位代表的意见，且同时使得总奖金数最少。每位员工奖金最少为元。
输入
第一行两个整数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。
【算法分析】
首先构图，若存在条件“a的钱比b多”则从b引一条有向指向a；然后拓扑排序，若无法完成排序则表示问题无解（存在圈）；若可以得到完整的拓扑序列，则按序列顺序进行递推：
设f[i]表示第i个人能拿的最少奖金数；
首先所有f[i]=100（题目中给定的最小值）；
然后按照拓扑顺序考察每个点i，若存在有向边(j,i)，则表示f[i]必须比f[j]大，因此我们令f[i] = Max { f[i] , f[j]+1 }即可；
递推完成之后所有f[i]的值也就确定了，而答案就等于f[1]+…+f[n]。