獎金，獎金英文
【問題描述】
由於無敵的凡凡在2005年世界英俊帥氣男總決選中勝出，Yali Company總經理Mr.Z心情好，決定給每位員工發獎金。公司決定以每個人本年在公司的貢獻為標准來計算他們得到獎金的多少。於是Mr.Z下令召開m方會談。每位參加會談的代表提出了自己的意見：“我認為員工a的獎金應該比b高！”Mr.Z決定要找出一種獎金方案，滿足各位代表的意見，且同時使得總獎金數最少。每位員工獎金最少為100元。
【輸入格式】
第一行兩個整數n,m，表示員工總數和代表數；以下m行，每行2個整數a,b，表示某個代表認為第a號員工獎金應該比第b號員工高。
【輸出格式】
若無法找到合理方案，則輸出“Poor Xed”；否則輸出一個數表示最少總獎金。
【輸入樣例】
2 1
1 2
【輸出樣例】
201
【數據規模】
80％的數據滿足n<=1000，m<=2000；100％的數據滿足n<=10000，m<=20000。
【算法分析】
首先構圖，若存在條件“a的錢比b多”則從b引一條有向指向a；然後拓撲排序，若無法完成排序則表示問題無解（存在圈）；若可以得到完整的拓撲序列，則按序列順序進行遞推：
設f[i]表示第i個人能拿的最少獎金數；
首先所有f[i]=100（題目中給定的最小值）；
然後按照拓撲順序考察每個點i，若存在有向邊(j,i)，則表示f[i]必須比f[j]大，因此我們令f[i] = Max { f[i] , f[j]+1 }即可；
遞推完成之後所有f[i]的值也就確定了，而答案就等於f[1]+…+f[n]。
部分大數據需要用差分約束系統這個我實在不會
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<stack>
5 using namespace std;
6 struct node
7 {
8 int u;
9 int v;
10 int next;
11 }edge[10001];
12 int head[10001];
13 int num=1;
14 int rudu[1001];
15 stack<int>s;
16 int money[10001];
17 int ans=0;
18 int main()
19 {
20 int n,m;
21 scanf("%d%d",&n,&m);
22 for(int i=1;i<=n;i++)money[i]=100;
23 for(int i=1;i<=n;i++)head[i]=-1;
24 for(int i=1;i<=m;i++)
25 {
26 scanf("%d%d",&edge[num].v,&edge[num].u);
27 edge[num].next=head[edge[num].u];
28 rudu[edge[num].v]++;
29 head[edge[num].u]=num++;
30 }
31 int tot=0;
32 for(int i=1;i<=n;i++)
33 {
34 if(rudu[i]==0)
35 {
36 s.push(i);
37 tot++;
38 }
39 }
40
41 while(s.size()!=0)
42 {
43 int p=s.top();
44 s.pop();
45 for(int i=head[p];i!=-1;i=edge[i].next)
46 {
47 if(money[edge[i].v]<money[edge[i].u]+1)
48 money[edge[i].v]=money[edge[i].u]+1;
49 rudu[edge[i].v]--;
50 if(rudu[edge[i].v]==0)
51 {
52 s.push(edge[i].v);
53 tot++;
54 }
55 }
56 }
57 if(tot!=n)printf("-1");
58 else
59 {
60 for(int i=1;i<=n;i++)
61 ans=ans+money[i];
62 printf("%d",ans);
63 }
64 return 0;
65 }
