AcWing 1192. 奖金
原题链接
简单
作者:
王小强
,
2021-02-07 15:38:46
,
所有人可见
,
阅读 242
学好算法,能当HR!!
(特别是Topologic Sorting)
#include <iostream>
#include <queue>
using namespace std;
int n, m, a, b;
int main(void) {
cin >> n >> m;
vector<int> indegrees(n + 1);
vector<vector<int>> g(n + 1);
while (m--) {
cin >> a >> b;
g[b].emplace_back(a);
++indegrees[a];
}
queue<pair<int, int>> q;
for (int i = 1; i <= n; ++i)
if (!indegrees[i]) q.emplace(i, 100);
// cost == (如果有合理方案的化,总共要分配多少奖金)
// num == (如果有合理方案的化, 分配奖金的人数)
int cost = 0, num = 0;
while (not q.empty()) {
const auto [cur, bonus] = q.front(); q.pop();
++num;
cost += bonus;
for (const auto& nei : g[cur])
if (!(--indegrees[nei])) q.emplace(nei, bonus + 1); // 就多一块钱 (不大气!!)
}
if (num == n) printf("%d", cost); else puts("Poor Xed");
return 0;
}