Codevs 4040 EZ系列之奖金

题目描述 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。

/*
用链表 做toposort
很裸没啥好说的
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
#define DATE 10005
#define INF 987654321
using namespace std;
int n,m,a,b,top,sum,money,tot;
//int stack[DATE];
bool map[DATE][DATE];
struct node {
    int to;
    int next;
};
node e[DATE];
int head[DATE];
int ans;
stack<int> s;
int rudu[DATE];
void topsort();
void add(int x,int y){
    e[++tot].to=y;
    e[tot].next=head[x];
    head[x]=tot;
} 
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        add(b,a);
        //map[b][a]=true;
        rudu[a]++;
    }
    topsort();
    return 0;
}
void topsort()
{
    int money=0;
    while(sum<n)
    {
        for(int i=1;i<=n;i++) {
            if(rudu[i]==0) {
                ans+=100+money;
                s.push(i);
                rudu[i]=INF;
                sum++;
            }
        }
        if(s.empty()) {
            printf("-1
");
            return;
        }
        while(!s.empty()) {
            int num=s.top();
            s.pop();
            for(int i=head[num];i;i=e[i].next) {
                //if(map[num][i])
                    rudu[e[i].to]--;
            }
        }
        money++;
    }
    cout<<ans;
    return;
}