【題目描述】
由于無敵的凡凡在2005年世界英俊帥氣男總決選中勝出，Yali Company總經理Mr.Z心情好，決定給每位員工發獎金。公司決定以每個人本年在公司的貢獻為標準來計算他們得到獎金的多少。
于是Mr.Z下令召開m方會談。每位參加會談的代表提出了自己的意見：“我認為員工a的獎金應該比b高！”Mr.Z決定要找出一種獎金方案，滿足各位代表的意見，且同時使得總獎金數最少。每位員工獎金最少為100元。
【輸入】
第一行兩個整數n,m，表示員工總數和代表數；
以下m行，每行2個整數a,b，表示某個代表認為第a號員工獎金應該比第b號員工高。
【輸出】
若無法找到合法方案，則輸出“-1”；否則輸出一個數表示最少總獎金。
輸入輸出樣例
reward.in
2 1
1 2
reward.out
201
【數據范圍】
80％的數據滿足n<=1000，m<=2000；
100％的數據滿足n<=10000，m<=20000。

個人解析:

?這道題就是拓撲排序。排的過程中，把自己所須的經費加上.

把最便宜的那個人作為起點。之后開始拓撲。每次加錢的時候可以先加基數100，之后那一層拓撲（同時有幾個入度為0的點）的時候把相應的 個數＊層數。就是第幾個加錢的，與第幾個加錢的人數的乘積。

1 #include<cstdio> 2 #include<algorithm> 3 #include<string.h> 4 using namespace std; 5 struct node{ 6 int next; 7 int v; 8 }edge[20010]; 9 int queue[10010]; 10 int head[10010],r[10010],c[10010]; 11 int n,m,cnt; 12 void add(int x,int y){ 13 edge[++cnt].next=head[x]; 14 edge[cnt].v=y; 15 head[x]=cnt; 16 } 17 int main() 18 { 19 scanf("%d%d",&n,&m); 20 int x,y; 21 memset(head,-1,sizeof(head)); 22 for(int i=1;i<=m;i++) 23 { 24 scanf("%d%d",&x,&y); 25 add(y,x); 26 r[x]++; 27 c[y]++; 28 } 29 int t,tot=0,money=0,k=0; 30 while(tot<n){ 31 t=0;//當前層里的入度為0的個數。 32 for(int i=1;i<=n;i++) 33 { 34 if(r[i]==0){ 35 t++;tot++;money+=100; 36 queue[0]++; //隊列[0]放的是隊列里元素的個數 37 queue[queue[0]]=i; 38 r[i]=-1; 39 } 40 } 41 if(t==0){ //出現環。 42 printf("Poor Xed"); 43 return 0; 44 } 45 money=money+k*t; 46 k++;//層數++。 47 for(int i=1;i<=queue[0];i++){ 48 for(int j=head[queue[i]];j!=-1;j=edge[j].next) 49 { 50 r[edge[j].v]--; //該點的下一個點的入度--。 51 } 52 } 53 queue[0]=0; //隊列清空。 54 } 55 printf("%d",money); 56 return 0; 57 }

?

轉載于:https://www.cnblogs.com/uncle-lu/p/5856235.html

總結

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

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