1424.獎金

Description
由于無敵的凡凡在2005年世界英俊帥氣男總決選中勝出，Yali Company總經理Mr.Z心情好，決定給每位員工發獎金。公司決定以每個人本年在公司的貢獻為標準來計算他們得到獎金的多少。
于是Mr.Z下令召開m方會談。每位參加會談的代表提出了自己的意見：“我認為員工a的獎金應該比b高！”Mr.Z決定要找出一種獎金方案，滿足各位代表的意見，且同時使得總獎金數最少。每位員工獎金最少為100元。

【數據范圍】
數據滿足n<=10000，m<=20000。

Input
第一行兩個整數n,m，表示員工總數和代表數；
以下m行，每行2個整數a,b，表示某個代表認為第a號員工獎金應該比第b號員工高。
Output
若無法找到合法方案，則輸出“Poor Xed”；否則輸出一個數表示最少總獎金。
Sample Input
Copy sample input to clipboard
2 1
1 2
Sample Output
201
算法中最關鍵的地方加上了注釋，注意看那就好了

#include <vector> #include <iostream> #include <cstring> #include <queue> using namespace std;const int MAXN = 10000+3; vector<int> node[MAXN]; int bonus[MAXN]; int inDegree[MAXN];int main (){memset(inDegree, 0, sizeof (inDegree));int n ,m,a,b;cin>> n >> m;while(m--){cin>> a>> b;node[b].push_back(a);inDegree[a]++;}queue<int> q;for (int i = 1; i <= n; ++i) if (!inDegree[i]) q.push(i);int ans = 100*n, sorted = 0;while(!q.empty() && sorted <= n){int now = q.front(); q.pop();ans += bonus[now]; sorted ++;for (int i = 0; i < node[now].size(); ++i) {inDegree[node[now][i]]--;if (inDegree[node[now][i]] == 0) q.push(node[now][i]); // 比它小的所有點都已經排好了bonus[node[now][i]] = bonus[now] + 1; }}if (sorted == n) cout << ans<< endl;else cout << "Poor Xed"<< endl; }

2018/3/22 更新復習一下。

做一個簡單的策略分析

#include <iostream> #include <cstring> #include <vector> #include <queue> using namespace std; const int MAXN = 10000 + 10; int indegree[MAXN]; // 記錄i的入度數目，即比他便宜的，卻還存在的點數 int bonus[MAXN]; vector<int> node[MAXN]; // 比i大點序列。 // 策略：先處理沒有任何更小的點。類似于逐步堆積一個堆。先將最底層建立起來，然后，通過建立起來的最小值來推理出其他的數值。 int main() {int n, m, a, b, ans, time, head;while (cin >> n >> m) {ans = n * 100;memset(indegree, 0, sizeof(indegree));memset(bonus, 0, sizeof(bonus));for (int i = 1; i <= n; ++i) node[i].clear();for (int i = 1; i <= m; ++i) {cin >> a >> b;indegree[a]++;node[b].push_back(a);}queue<int> q; // BFS處理DAGfor (int i = 1; i <= n; ++i) if (indegree[i] == 0) q.push(i);time = 0; // countwhile (!q.empty() && time <= n) {head = q.front(); q.pop();ans += bonus[head]; time++;for (int i = 0; i < node[head].size(); ++i) {indegree[node[head][i]] --; if (indegree[node[head][i]] == 0) q.push(node[head][i]);else if (indegree[node[head][i]] < 0) time = n + 1;bonus[node[head][i]] = bonus[head] + 1;}}if (time == n) cout << ans<< endl;else cout << "Poor Xed" << endl;} }

最后，老套路，宣傳一波自己的公眾號！（求關注哇！）
本人中大一肥宅，歡迎大家關注，請掃下面的二維碼(〃’▽’〃)

如果覺得有幫助的話，可以掃碼，贊賞鼓勵一下！謝謝！

總結

以上是生活随笔為你收集整理的【topoSort拓扑排序】1424. 奖金（简单题目看拓扑排序）的全部內容，希望文章能夠幫你解決所遇到的問題。

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