本文共 1142 字，大约阅读时间需要 3 分钟。
老板发工资，存在a>b,每个人的保底工资为888，给出n个人的工资关系，求老板发的最少的工资。
拓扑排序，有环则-1。
同时，给的顺序是从大到小，变成从小到大的顺序，求起来简单。
#include #include #include #include #include #include #include #include using namespace std;typedef long long LL;const int MAXN = 1e4 + 10;vector Group[MAXN];int in[MAXN];int value[MAXN];int n, m;bool topo(){ queue que; int cnt = 0; for (int i = 1;i <= n;i++) if (in[i] == 0) { que.push(i); value[i] = 888; } while (!que.empty()) { int now = que.front(); cnt++; que.pop(); for (auto x : Group[now]) { if (--in[x] == 0) { que.push(x); value[x] = value[now] + 1; } } } if (cnt == n) return true; return false;}int main(){ int l, r; while (~scanf("%d%d", &n, &m)) { for (int i = 1;i <= n;i++) Group[i].clear(); memset(in, 0, sizeof(in)); for (int i = 1; i <= m; i++) { scanf("%d%d", &l, &r); Group[r].push_back(l); in[l]++; } int res = 0; if (topo()) { for (int i = 1;i <= n;i++) res += value[i]; } else res = - 1; cout << res << endl; } return 0;}
转载于:https://www.cnblogs.com/YDDDD/p/10488026.html