奖金【拓扑排序】【DP】

拓扑排序】【DP】"/>

奖金【拓扑排序】【DP】

>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

>解题思路
拓扑排序模板（+DP）。

>代码

#include<iostream>
#include<cstdio>
using namespace std;
struct ooo
{int to,next;
}a[200005];
int n,m,head,tail,h[100005],st[100005],tt,aa,bb,c[100005],f[100005],ans;
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d%d",&aa,&bb);a[++tt].to=aa; a[tt].next=h[bb]; h[bb]=tt;c[aa]++;}for(int i=1;i<=n;i++)if(!c[i]) st[++tail]=i,f[i]=100; //每人最少得到100元while(head<tail){head++;for(int i=h[st[head]];i;i=a[i].next){f[a[i].to]=max(f[a[i].to],f[st[head]]+1); //DP:a的奖金比b最少高1元c[a[i].to]--; //入度--if(!c[a[i].to]) st[++tail]=a[i].to;}}if(tail!=n){printf("-1");return 0;}for(int i=1;i<=n;i++)ans+=f[i];printf("%d",ans);return 0;
}