早教吧作业答案频道 -->数学-->
算法设计题三:基于图论的奖金分配问题由于无敌的凡凡在2005年世界英俊帅气男总决选中胜出,YaliCompany总经理Mr.Z心情好,决定给每位员工发奖金.公司决定以每个人本年在公司的贡献为标准
题目详情
算法设计题三:基于图论的奖金分配问题
由于无敌的凡凡在2005年世界英俊帅气男总决选中胜出,Yali Company总经理Mr.Z心情好,决定给每位员工发奖金.公司决定以每个人本年在公司的贡献为标准来计算他们得到奖金的多少.
于是Mr.Z下令召开m方会谈.每位参加会谈的代表提出了自己的意见:“我认为员工a的奖金应该比b高!”Mr.Z决定要找出一种奖金方案,满足各位代表的意见,且同时使得总奖金数最少.每位员工奖金最少为100元.
【输入】
第一行两个整数n,m,表示员工总数和代表数;
以下m行,每行2个整数a,b,表示某个代表认为第a号员工奖金应该比第b号员工高.
【输出】
若无法找到合法方案,则输出“Poor Xed”;否则输出一个数表示最少总奖金.
由于无敌的凡凡在2005年世界英俊帅气男总决选中胜出,Yali Company总经理Mr.Z心情好,决定给每位员工发奖金.公司决定以每个人本年在公司的贡献为标准来计算他们得到奖金的多少.
于是Mr.Z下令召开m方会谈.每位参加会谈的代表提出了自己的意见:“我认为员工a的奖金应该比b高!”Mr.Z决定要找出一种奖金方案,满足各位代表的意见,且同时使得总奖金数最少.每位员工奖金最少为100元.
【输入】
第一行两个整数n,m,表示员工总数和代表数;
以下m行,每行2个整数a,b,表示某个代表认为第a号员工奖金应该比第b号员工高.
【输出】
若无法找到合法方案,则输出“Poor Xed”;否则输出一个数表示最少总奖金.
▼优质解答
答案和解析
按M个代表的意见建图,若图中有环则无解,否则拓扑排序之后算出总奖金.
看了 算法设计题三:基于图论的奖金...的网友还看了以下:
南阳理工acm-icpc关于521”这道题输入多组数据,如果每一组都重新计算的话必定超时.所以只能 2020-04-07 …
声学物理计算题某同学站在铁路旁,他看见远处的铁道工人用锤头向铁轨敲一下,听见了第一次敲击声,过了一 2020-05-16 …
那个数字写法正确,是题一?还是题二?题一:我单位结算百分比率为(大写)零点叁伍(小写:0.35)在 2020-06-09 …
请教估算理综成绩:希望计算0.4的物理加0.333的化学加0.267的生物分数,函数怎么设置.能不 2020-07-19 …
成本管理计算题某产品经三道工序加工而成.每道工序的工时定额分别为15小时、25小时、10小时.各道 2020-07-26 …
挖掘机台时单价如何计算?等某水利工程人工预算单价中级工5.62元/工时,0#柴油4.80元/kg, 2020-07-26 …
造价员基础题,这题有答案但是不知道怎么算的出来的,求过程已知某分项工程的基本用工是1.2工日/m,超 2020-10-30 …
并联串联的概率计算元件1,2并联,元件3,4串联的线路,元件可以工作的概率都是0.9,求系统可以工作 2020-11-03 …
(1)求甲,乙两队单独完成这项工程所需多少天?(2)已知甲队每天施工费用0.67万元,乙队每天施工费 2020-11-06 …
一道物理计算题木工用49牛的力锯木块,每拉一次行程为0.5米,每拉一次行程锯入木块2毫米,如果他在4 2020-11-08 …