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。

.
.
.
.
.
.
分析
正解：拓撲排序
數據過水，可用深搜。
數組竟開這么大能過

.
.
.
.
.
程序：

#include<iostream> #include<cstdio> #include<cstring> using namespace std;int n,m,c[10010],a[10010][10],s[10010],bz=0; bool f[10010];void dfs(int i,int money) {if (s[i]<=money) s[i]=money+1; else return;f[i]=true;for (int j=1;j<=c[i];j++) if (f[a[i][j]]==false) dfs(a[i][j],s[i]); else{printf("-1");bz=1;return;}f[i]=false; }int main() {freopen("reward.in","r",stdin);freopen("reward.out","w",stdout);scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int u,v;scanf("%d%d",&u,&v);c[v]++;a[v][c[v]]=u;}for (int i=1;i<=n;i++)dfs(i,99);int ans=0;for (int i=1;i<=n;i++)ans+=s[i];if (bz==0) printf("%d",ans);fclose(stdin);fclose(stdout);return 0; }

轉載于:https://www.cnblogs.com/YYC-0304/p/11094918.html

總結

以上是生活随笔為你收集整理的奖金的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。