本文共 1025 字，大约阅读时间需要 3 分钟。

08年东莞特长生 奖金

Description

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

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

Input

两个整数n,m，表示员工总数和代表数；

Output

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

Sample Input

2 11 2

Sample Output

201

Hint

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

解题思路

BFS+拓扑

#include
   
    #include
    
     using namespace std;int n,m,a[100010],b[100010];int tot,head[100010],f[100010];int ans,t;struct abc{   	int to,next;}s[200010];void add(int x,int y){   	s[++tot]=(abc){   y,head[x]};	head[x]=tot;}void bfs(){   	int tl=0,hd=0;	for(int i=1;i<=n;i++)		if(b[i]==0)		{   			tl++;			f[tl]=i;			a[i]=0;		}	if(tl==0)	{   		cout<<-1<
     
      >n>>m;	for(int i=1;i<=m;i++)	{   		int x,y;		scanf("%d%d",&y,&x);		add(x,y);		b[y]++;	}	bfs();	if(t)		return 0;	for(int i=1;i<=n;i++)	{   		if(b[i]!=0)		{   			ans=-1;			break;		}		ans+=100+a[i];	}	cout<
      
       <