首页 > 代码库 > 4040 EZ系列之奖金

4040 EZ系列之奖金

2024-09-14 21:19:34   220人阅读

4040 EZ系列之奖金

 

时间限制: 1 s
空间限制: 64000 KB
题目等级 : 钻石 Diamond
 
题目描述 Description

由于无敌的WRN在2015年世界英俊帅气男总决选中胜出，EZ总经理Mr.Lin心情好，决定给每位员工发奖金。EZ决定以每个人本年在EZ的贡献为标准来计算他们得到奖金的多少。

于是Mr.Lin下令召开m方会谈。每位参加会谈的代表提出了自己的意见：“我认为学生a的奖金应该比b高！”Mr.Lin决定要找出一种奖金方案，满足各位代表的意见，且同时使得总奖金数最少。每位学生奖金最少为100元。

 

输入描述 Input Description

第一行两个整数n,m，表示学生总数和代表数；

以下m行，每行2个整数a,b，表示某个代表认为第a号学生奖金应该比第b号学生高。

 

输出描述 Output Description

若无法找到合法方案，则输出“-1”；否则输出一个数表示最少总奖金。

 

样例输入 Sample Input

2 1

1 2

样例输出 Sample Output

201

数据范围及提示 Data Size & Hint

80％的数据满足n<=1000，m<=2000；

100％的数据满足n<=10000，m<=20000。

 

 T了两个点，我也没办法了，stl，人工栈都过不了

 

  1 #include<iostream>  2 #include<cstdio>  3 using namespace std;  4 int top=0;  5 struct sta  6 {  7     int sz[100001];  8     int topp()  9     { 10         return sz[top]; 11     } 12     void push(int x){ 13          sz[++top]=x; 14     } 15     void pop(){ 16         if(top>0) 17         top--; 18     } 19     void cl() 20     { 21         top=0; 22     } 23     int size(){ 24         return top; 25     } 26 }stack; 27 struct node{ 28     int u,v,next; 29 }edge[100001]; 30 int rd[100001],head[100001],son[100001];int money=0,step=0,monney[100001]; 31 int n,m,num=1; 32 void add_edge(int x,int y) 33 { 34     edge[num].u=x; 35     edge[num].v=y; 36     edge[num].next=head[x]; 37     head[x]=num++; 38 } 39 void in() 40 { 41     scanf("%d%d",&n,&m); 42     for(int i=1;i<=n;i++) 43     { 44         head[i]=-1; 45         monney[i]=100; 46     } 47     int x,y; 48     for(int i=1;i<=m;i++) 49     { 50         scanf("%d%d",&x,&y); 51         add_edge(y,x); 52         rd[x]++; 53     } 54 } 55 int sum=0; 56 void topsort() 57 { 58     for(int i=1;i<=n;i++) 59     { 60         if(rd[i]==0) 61         { 62             stack.push(i); 63             sum++; 64         } 65     } 66     int step; 67     while(stack.size()!=0) 68     { 69         step=stack.topp(); 70         stack.pop(); 71         for(int i=head[step];i!=-1;i=edge[i].next) 72         { 73              74             if(monney[edge[i].v]<monney[edge[i].u]+1) 75             { 76                 monney[edge[i].v]=monney[edge[i].u]+1; 77             } 78             rd[edge[i].v]--; 79             if(rd[edge[i].v]==0) 80             { 81             stack.push(edge[i].v); 82             sum++; 83             } 84         } 85     } 86     if(sum!=n)cout<<"-1"; 87     else  88     { 89         for(int i=1;i<=n;i++) 90         money+=monney[i]; 91         cout<<money<<endl; 92     } 93     return; 94 } 95 int main() 96 { 97     in(); 98     topsort(); 99     return 0;100 }

 

 

 

 

4040 EZ系列之奖金


联系
我们