首页 > > 程序设计 > C/C++ >

奖金

2018-06-17 22:48:46来源：未知阅读 ()

【问题描述】

　　由于无敌的凡凡在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 }