奖金

【问题描述】

  由于无敌的凡凡在2005年世界英俊帅气男总决选中胜出,Yali Company总经理Mr.Z心情好,决定给每位员工发奖金。公司决定以每个人本年在公司的贡献为标准来计算他们得到奖金的多少。于是Mr.Z下令召开m方会谈。每位参加会谈的代表提出了自己的意见:“我认为员工a的奖金应该比b高!”Mr.Z决定要找出一种奖金方案,满足各位代表的意见,且同时使得总奖金数最少。每位员工奖金最少为100元。

【输入格式】

  第一行两个整数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]。

部分大数据需要用差分约束系统这个我实在不会

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<stack>
 5 using namespace std;
 6 struct node
 7 {
 8     int u;
 9     int v;
10     int next;
11 }edge[10001];
12 int head[10001];
13 int num=1;
14 int rudu[1001];
15 stack<int>s;
16 int money[10001];
17 int ans=0;
18 int main()
19 {
20     int n,m;
21     scanf("%d%d",&n,&m);
22     for(int i=1;i<=n;i++)money[i]=100;
23     for(int i=1;i<=n;i++)head[i]=-1;
24     for(int i=1;i<=m;i++)
25     {
26         scanf("%d%d",&edge[num].v,&edge[num].u);
27         edge[num].next=head[edge[num].u];
28         rudu[edge[num].v]++;
29         head[edge[num].u]=num++;
30     }
31     int tot=0;
32     for(int i=1;i<=n;i++)
33     {
34         if(rudu[i]==0)
35         {
36             s.push(i);
37             tot++;
38         }
39     }
40     
41     while(s.size()!=0)
42     {
43         int p=s.top();
44         s.pop();
45         for(int i=head[p];i!=-1;i=edge[i].next)
46         {
47             if(money[edge[i].v]<money[edge[i].u]+1)
48             money[edge[i].v]=money[edge[i].u]+1;
49             rudu[edge[i].v]--;
50             if(rudu[edge[i].v]==0)
51             {
52                 s.push(edge[i].v);
53                 tot++;
54             }
55         }
56     }
57     if(tot!=n)printf("-1");
58     else 
59     {
60         for(int i=1;i<=n;i++)
61         ans=ans+money[i];
62         printf("%d",ans);
63     }
64     return 0;
65 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ml

hdu----(4522)湫湫系列故事——过年回家(最短路)

湫湫系列故事——过年回家 Time Limit: 500/200 MS (Java/Others)    Memory Limit: 65535/32768 K...

2896
来自专栏Web行业观察

盘点那些奇形怪状的编程语言

有的语言是多面手,在很多不同的领域都能派上用场。这类编程语言叫 general-purpose language,简称 GPL。大家学过的编程语言很多都属于这一...

2452
来自专栏数据结构与算法

2924 数独挑战

2924 数独挑战  时间限制: 1 s  空间限制: 1000 KB  题目等级 : 钻石 Diamond 题解  查看运行结果 题目描述 Descripti...

2913
来自专栏LinkedBear的个人空间

设计模式笔记(三)——建造者模式 原

将一个复杂对象的构建与它的表示分离,使得同样的构建过程可以创建不同的表示。建造者模式使用多个简单的对象一步一步构建成一个复杂的对象。

682
来自专栏HTML5学堂

JavaScript基础考核真题——你能全做对吗?

正文 JavaScript基础考核真题——你能全做对吗。刘国利 - 独行冰海 : 每位讲师在授课、管理的同时,还需要不断的涉猎各种知识,提升本职技术。本文章的考...

2986
来自专栏数据结构与算法

1095 火星人

1095 火星人 2004年NOIP全国联赛普及组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 D...

35610
来自专栏noteless

抽象工厂模式 创建型 设计模式(四)

所有的ConcreteCreator的返回类型都是Product,因为抽象工厂角色Creator就是返回Product 

572
来自专栏编程

知道这几点你就学会了Python!

由于Python目前在各个领域都比较火,尤其是人工智能和量化金融方面的应用,更让人趋之若鹜,还不会Python的你是不是落伍了呢。下面就是我的不装逼教你学Pyt...

2255
来自专栏C语言及其他语言

初学C语言的学习计划

背景:很多同学在学习C语言的过程中,常常会遇到这样的问题,即“教材看完了,知识点也懂,但写不出来程序”,这段时间,我们通过长期与有多年C语言研究经验的教授、教师...

3594
来自专栏小詹同学

Python系列之六——拿什么拯救你?我的大脑

我一定是智障了,话不多说,上图上图~ ? 就是这样10个选择题,你没有看错,我一定是个智障了~佩服不用穷举,也不用参考网上的大...

3644

扫码关注云+社区

领取腾讯云代金券