奖金

广搜一层层做

#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> e[10000 + 5];
int inD[10000 + 5]; // 入度
queue<int> q;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int a, b; // a>b;
        cin >> a >> b;
        e[b].push_back(a);
        inD[a]++;
    }
    // 初始入度为0的人
    for (int i = 1; i <= n; i++)
        if (inD[i] == 0)
            q.push(i);
    int cash = 100; // 当前工资
    int ans = 0;    // 总工资
    int cnt = 0;    // 给几个人发了工资
    while (!q.empty())
    {
        int len = q.size();
        ans += len * cash;
        cash += 1;
        for (int t = 0; t < len; t++)
        {
            int u = q.front();
            q.pop();
            cnt++;
            for (int i = 0; i < e[u].size(); i++)
            {
                int v = e[u][i];
                inD[v]--;
                if (inD[v] == 0)
                    q.push(v);
            }
        }
    }
    if (cnt == n)
        cout << ans << "\n";
    else
        cout << "Poor Xed\n";
    return 0;
}

正常广搜做

#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> e[10000 + 5];
int inD[10000 + 5]; // 入度
int a[10000 + 5];   // 记录每个人发的钱
queue<int> q;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int a, b; // a>b;
        cin >> a >> b;
        e[b].push_back(a);
        inD[a]++;
    }
    // 初始入度为0的人
    int ans = 0; // 总工资
    for (int i = 1; i <= n; i++)
        if (inD[i] == 0)
        {
            q.push(i);
            a[i] = 100;
            ans += 100;
        }
    int cnt = 0; // 给几个人发了工资
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        cnt++;
        for (int i = 0; i < e[u].size(); i++)
        {
            int v = e[u][i];
            inD[v]--;
            if (inD[v] == 0)
            {
                q.push(v);
                a[v] = a[u] + 1;
                ans += a[v];
            }
        }
    }
    if (cnt == n)
        cout << ans << "\n";
    else
        cout << "Poor Xed\n";
    return 0;
}