首页 > 代码库 > #图# #拓扑排序# ----- 奖金

#图# #拓扑排序# ----- 奖金

2024-08-18 20:18:27   221人阅读

奖金
【题目描述】
由于无敌的凡凡在2005年世界英俊帅气男总决选中胜出，Yali Company总经理Mr.Z心情好，决定给每位员工发奖金。公司决定以每个人本年在公司的贡献为标准来计算他们得到奖金的多少。
于是Mr.Z下令召开m方会谈。每位参加会谈的代表提出了自己的意见：“我认为员工a的奖金应该比b高！”Mr.Z决定要找出一种奖金方案，满足各位代表的意见，且同时使得总奖金数最少。每位员工奖金最少为100元。
【输入】
第一行两个整数n,m，表示员工总数和代表数；
以下m行，每行2个整数a,b，表示某个代表认为第a号员工奖金应该比第b号员工高。
【输出】
若无法找到合法方案，则输出“-1”；否则输出一个数表示最少总奖金。
输入输出样例
reward.in
2 1
1 2
reward.out
201
【数据范围】
80％的数据满足n<=1000，m<=2000；
100％的数据满足n<=10000，m<=20000。

有环无解 。

 

 1 #include<cstdio>
 2 int n,m;
 3 int cnt,w=100,w1,t;
 4 int r[10005],c[10005],ans[10005],a[10005][5005];
 5 
 6 int main(){
 7     scanf("%d%d",&n,&m);
 8     for(int i=1;i<=m;++i){
 9         int x,y;
10         scanf("%d%d",&x,&y);
11         r[x]++;
12         c[y]++;
13         a[y][c[y]]=x;
14     }
15     for(int i=1;i<=n;++i)if(r[i]==0)ans[++cnt]=i;
16     if(!cnt){
17         printf("-1");
18         return 0;
19     }
20     
21     int x;
22     while(t<=n){
23         x=ans[cnt];
24         cnt--;
25         t++;
26         for(int i=1;i<=c[x];++i){
27             r[a[x][i]]--;
28             if(r[a[x][i]]==0){
29                 ans[++cnt]=a[x][i];
30                 w1++;
31                 w=w+100+w1;
32             }
33         }
34     }
35     printf("%d",w);
36     return 0;
37 }

 

#图# #拓扑排序# ----- 奖金


联系
我们