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代码:

 #include<iostream>
#include<cstdio>
using namespace std;
int top=;
struct sta
{
int sz[];
int topp()
{
return sz[top];
}
void push(int x){
sz[++top]=x;
}
void pop(){
if(top>)
top--;
}
void cl()
{
top=;
}
int size(){
return top;
}
}stack;
struct node{
int u,v,next;
}edge[];
int rd[],head[],son[];int money=,step=,monney[];
int n,m,num=;
void add_edge(int x,int y)
{
edge[num].u=x;
edge[num].v=y;
edge[num].next=head[x];
head[x]=num++;
}
void in()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
{
head[i]=-;
monney[i]=;
}
int x,y;
for(int i=;i<=m;i++)
{
scanf("%d%d",&x,&y);
add_edge(y,x);
rd[x]++;
}
}
int sum=;
void topsort()
{
for(int i=;i<=n;i++)
{
if(rd[i]==)
{
stack.push(i);
sum++;
}
}
int step;
while(stack.size()!=)
{
step=stack.topp();
stack.pop();
for(int i=head[step];i!=-;i=edge[i].next)
{ if(monney[edge[i].v]<monney[edge[i].u]+)
{
monney[edge[i].v]=monney[edge[i].u]+;
}
rd[edge[i].v]--;
if(rd[edge[i].v]==)
{
stack.push(edge[i].v);
sum++;
}
}
}
if(sum!=n)cout<<"-1";
else
{
for(int i=;i<=n;i++)
money+=monney[i];
cout<<money<<endl;
}
return;
}
int main()
{
in();
topsort();
return ;
}
05-11 21:57