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，人工栈都过不了

woc，t的原因是数组开小了....不知为什么codevs报t

AC代码：

  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 }