算法设计题三:基于图论的奖金分配问题
由于无敌的凡凡在2005年世界英俊帅气男总决选中胜出,Yali Company总经理Mr.Z心情好,决定给每位员工发奖金.公司决定以每个人本年在公司的贡献为标准来计算他们得到奖金的多少.
于是Mr.Z下令召开m方会谈.每位参加会谈的代表提出了自己的意见:“我认为员工a的奖金应该比b高!”Mr.Z决定要找出一种奖金方案,满足各位代表的意见,且同时使得总奖金数最少.每位员工奖金最少为100元.
【输入】
第一行两个整数n,m,表示员工总数和代表数;
以下m行,每行2个整数a,b,表示某个代表认为第a号员工奖金应该比第b号员工高.
【输出】
若无法找到合法方案,则输出“Poor Xed”;否则输出一个数表示最少总奖金.
人气:406 ℃ 时间:2020-05-23 15:59:31
解答
按M个代表的意见建图,若图中有环则无解,否则拓扑排序之后算出总奖金.
推荐
- 基于图论的奖金分配问题
- 图论:最短路算法有哪些以及它们的比较?
- 图论-关于dijkstra算法,
- 如何判断一个图是否是连着的?图论,算法
- 假设长度大于1的单循环链表中,既无头结点,也无头指针,p为指向该链表中某一结点的指针,编写一个算法在p之前插入一个值为x的结点.
- 一个长6米,宽3米,高2米的房间,放一根竹竿,竹竿最长多少米?
- (2012•顺义区二模)下列关于有机物的叙述正确的是( ) A.汽油、柴油和植物油都是碳氢化合物 B.棉花和合成纤维的主要成分均为纤维素 C.乙烯和苯蒸气都能使溴水褪色,不能鉴别乙烯
- 什么情况下1+1等于3?
猜你喜欢