題目 3129:
信息學(xué)奧賽一本通T1352-獎金
時間限制: 2s
內(nèi)存限制: 192MB 提交: 88 解決: 28
題目描述
由于無敵的凡凡在2005年世界英俊帥氣男總決選中勝出,Yali Company總經(jīng)理Mr.Z心情好,決定給每位員工發(fā)獎金。公司決定以每個人本年在公司的貢獻為標準來計算他們得到獎金的多少。
于是Mr.Z下令召開m方會談。每位參加會談的代表提出了自己的意見:“我認為員工a的獎金應(yīng)該比b高!”Mr.Z決定要找出一種獎金方案,滿足各位代表的意見,且同時使得總獎金數(shù)最少。每位員工獎金最少為100元。
輸入格式
第一行兩個整數(shù)n,m,表示員工總數(shù)和代表數(shù);
以下m行,每行2個整數(shù)a,b,表示某個代表認為第a號員工獎金應(yīng)該比第b號員工高。
輸出格式
若無法找到合理方案,則輸出“Poor Xed”;否則輸出一個數(shù)表示最少總獎金。
提示
【數(shù)據(jù)規(guī)?!?br />
80%的數(shù)據(jù)滿足:n≤1000,m≤2000;
100%的數(shù)據(jù)滿足:n≤10000,m≤20000。