題目

由于公司在2013年的銷售業務成績優秀，公司總經理心情大好，決定給每位員工發獎金。公司決定以每個人本年在公司的貢獻為標準來計算他們得到獎金的多少。于是總經理下令召開 m 方會談。每位參加會談的代表提出了自己的意見：“我認為員工 a 的獎金應該比 b 高！”。總經理決定要找出一種獎金方案，滿足各位代表的意見，且同時使得總獎金數最少。每位員工獎金最少為100元。
輸入格式
第一行兩個整數 n 和 m，表示員工總數和代表數；
接下來有 m 行，每行 2 個整數 a 和 b，表示某個代表認為第 a 號員工獎金應該比第 b 號員工高。
輸出格式
若無法找到合理方案，則輸出“Poor Xed”；否則輸出一個數表示最少總獎金。
樣例數據 1
輸入
2 1
1 2
輸出
201
備注
【數據規模】
80％的數據滿足：n<=1000，m<=2000；
100％的數據滿足：n<=10000，m<=20000。

很簡單的一道拓撲排序

如果A的工資要比B高，那就從B向A連一條邊

然后從入度為0的點開始統計

然后用$f$來記錄每個點的工資，當從點i指向點j的時候$f[j]=max(f[j],f[i]+1)$

最后的答案就是$\sum f[i],1<=i<=n$

因為直接雙層循環要超時，所以只能循環隊列來做，但如果m，n到了151^515的時候，就只能用特殊的數據結構來維護入度了

若一次循環中沒有入度為0的點了，而還有點未處理，則有環，無解

代碼

#include<bits/stdc++.h> using namespace std; inline int read(){char ch=getchar();int res=0;while(!isdigit(ch)) ch=getchar();while(isdigit(ch)) res=(res<<3)+(res<<1)+(ch^48),ch=getchar();return res; } int adj[20005],nxt[20005],to[20005],dep[10005],in[10005],f[10005],n,m,cnt; inline int sum(){int ans=0;for(int i=1;i<=n;i++)ans+=f[i];return ans; } inline void addedge(int u,int v) {nxt[++cnt]=adj[u],adj[u]=cnt,to[cnt]=v,in[v]++; } inline void _(int k) {for(int e=adj[k];e;e=nxt[e]){in[to[e]]--;f[to[e]]=max(f[to[e]],f[k]+1);} } inline bool solve(){int tot=0;while(tot<n){int t=0;for(int i=1;i<=n;i++){if(in[i]==0){t++,tot++;in[i]=1<<30;_(i);}}if(!t){return false;}}return true; } int main(){n=read(),m=read();int a,b;for(int i=1;i<=n;i++)f[i]=100;for(int i=1;i<=m;i++){a=read(),b=read();addedge(b,a);}if(solve()) cout<<sum()<<endl;else cout<<"Poor Xed"<<'\n';return 0; }

轉載于:https://www.cnblogs.com/stargazer-cyk/p/10366500.html

總結

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

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