奖金

原题链接

题目描述

由于无敌的凡凡在2005年世界英俊帅气男总决选中胜出，Yali Company总经理Mr.Z心情好，决定给每位员工发奖金。

公司决定以每个人本年在公司的贡献为标准来计算他们得到奖金的多少。

于是Mr.Z下令召开 m 方会谈。

每位参加会谈的代表提出了自己的意见：“我认为员工 a 的奖金应该比 b 高！”

Mr.Z决定要找出一种奖金方案，满足各位代表的意见，且同时使得总奖金数最少。

每位员工奖金最少为100元，且必须是整数。

---

拓扑求最长路

模板。

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 10010, M = 20010;

int n, m;
int h[N], e[M], ne[M], idx;
int d[N], dist[N];
vector<int> v;

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void topsort() {
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (!d[i]) {
            q.push(i);
            dist[i] = 100;
        }

    while (q.size()) {
        int u = q.front();
        q.pop();

        v.push_back(u);

        for (int i = h[u]; i != -1; i = ne[i]) {
            int j = e[i];
            if (--d[j] == 0) q.push(j);
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    memset(h, -1, sizeof h);
    cin >> n >> m;
    while (m--) {
        int a, b;
        cin >> a >> b;
        add(b, a);
        d[a]++;
    }

    topsort();

    if (v.size() != n) {
        cout << "Poor Xed" << endl;
        return 0;
    }

    for (int i = 0; i < v.size(); i++) {
        int j = v[i];
        for (int k = h[j]; k != -1; k = ne[k])
            dist[e[k]] = max(dist[e[k]], dist[j] + 1);
    }

    int res = 0;
    for (int i = 1; i <= n; i++) res += dist[i];
    cout << res << endl;

    return 0;
}