奖金

Description

由于无敌的凡凡在2005年世界英俊帅气男总决选中胜出，Yali Company总经理Mr.Z心情好，决定给每位员工发奖金。公司决定以每个人本年在公司的贡献为标准来计算他们得到奖金的多少。
　　于是Mr.Z下令召开m方会谈。每位参加会谈的代表提出了自己的意见：“我认为员工a的奖金应该比b高！”Mr.Z决定要找出一种奖金方案，满足各位代表的意见，且同时使得总奖金数最少。每位员工奖金最少为100元。

Input

两个整数n,m，表示员工总数和代表数；
以下m行，每行2个整数a,b，表示某个代表认为第a号员工奖金应该比第b号员工高。

Output

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

Sample Input

2 1
1 2

Sample Output

201

Hint

80％的数据满足n<=1000，m<=2000；
100％的数据满足n<=10000，m<=20000。

解题思路

建议先自己出一个大一点的数据，再画个图

这题就是拓扑排序+dp
用拓扑排序来判断环（主）和算每位员工的钱（辅）
用dp来算每位员工的钱（主）

AC代码

#include<cstdio>
#include<iostream>
using namespace std;
long long n,m,x,y,h,t,s,tot,c[10005],p[10005],f[10005],du[10005],head[10005];
struct node
{
   
	int to,next;
}a[40005];
void add(int x,int y)//方便拓扑排序的邻接表
{
   
	a[++tot]=(node){
   y,head[x]};
	head[x]=tot;
}
void tp()//拓扑排序
{
   
	for(int i=1;i<=n;i++)if(du[i]==0){
   p[++t]=i;c[i]=1;};//入度为0的都进队
	while(h<t)
	{
   
		h++;//头++
		for(int i=head[p[h]];i;i=a[i].next)//找与它相连的边
		 if(c[a[i].to]==0)//免得又进循环，多算一次dp
		 {
   
		 	f[a[i].to]=max(f[a[i].to],f[p[h]]+1);//dp，由父节点加过来，注意要和自己比较
			du[a[i].to]--;//删边，就是入度-1
			if(du[a[i].to]==0)//如果入度为0
			{
   
				c[a[i].to]=1;//标记
				p[++t]=a[i].to;//清空
			}
		 } 	
	}
}
int main()
{
   
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
   
		cin>>x>>y;
		add(y,x);//反过来，根比子小
		du[x]++;//入度++
	}
	for(int i=1;i<=n;i++)f[i]=100;//初值
	tp();//拓扑
	for(int i=1;i<=n;i++)//输出
	 if(du[i]!=0){
   cout<<-1;return 0;}//如果还有入度不为0，就说明形成了环
	 else s+=f[i];
	cout<<s; 
}

谢谢