【例4-13】奖金

题目描述

公司要给 n 个员工发奖金，每人每张至少 100 元。m 条意见形如 “a 应该比 b 高”，即 $pay[a] \geqslant pay[b] + 1$ 。求满足所有意见的总奖金最小值；若约束互相矛盾，输出 Poor Xed。n≤10000，m≤20000。

输入：第一行 n m；之后 m 行每行 a b。输出：最少总奖金或 Poor Xed。

样例：2 1\n1 2 → 201（pay[2]=100，pay[1]=101）。

思路

把"a 高于 b"建成反向边 b→a，沿这条方向 Kahn 拓扑排序：入度归零的人直接取 100 元，出队时把后继 v 抬到 $\max(pay[v], pay[u]+1)$ ；最后若出队人数 < n 说明有环，输出 Poor Xed，否则累加 pay 即为最小总奖金。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 06:35
# update_at: 2026-09-30 06:35

import sys
from collections import deque


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)

    # 约束 “a 比 b 高” 改写成 b -> a：沿这个方向拓扑排序，才能先定低薪再定高薪
    succ: list[list[int]] = [[] for _ in range(n + 1)]
    indeg = [0] * (n + 1)
    for _ in range(m):
        a, b = next(data), next(data)
        succ[b].append(a)
        indeg[a] += 1

    pay = [100] * (n + 1)  # 每位员工奖金最少 100 元
    q = deque(i for i in range(1, n + 1) if not indeg[i])
    done = 0
    while q:
        u = q.popleft()
        done += 1
        for v in succ[u]:
            pay[v] = max(pay[v], pay[u] + 1)  # 至少比更低的人多 1 元
            indeg[v] -= 1
            if not indeg[v]:  # 所有更低的人都已定薪，v 才能入队定薪
                q.append(v)

    if done < n:  # 还有人没轮到：约束成环，互相矛盾
        print("Poor Xed")
    else:
        print(sum(pay[1:]))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 11:24
 * update_at: 2026-10-05 11:24
 */

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

typedef long long ll;

const int MAXN = 10005;      // 员工数 n <= 10000
const int MAXM = 20005;      // 意见条数 m <= 20000

// 反向图：约束 "a 应该比 b 高" 改写成 b -> a，沿这条边方向拓扑，才能先定低薪再定高薪。
int head[MAXN], to[MAXM], nxt[MAXM], edge_cnt;
int indeg[MAXN];             // 入度：a 的入度 = 让 a 必须更高的"下级"个数
ll pay[MAXN];               // 每人最终奖金；用 ll 累加并兼容极端值

// 加一条 u -> v 的有向边（u 工资更低 / v 工资更高）。
void add_edge(int u, int v) {
    edge_cnt++;
    to[edge_cnt] = v;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

int n, m;

void read_input() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) head[i] = 0, indeg[i] = 0;
    edge_cnt = 0;
    for (int i = 1; i <= m; i++) {
        int a, b;             // a 应该比 b 高 => 建边 b -> a
        cin >> a >> b;
        add_edge(b, a);
        indeg[a]++;
    }
}

void solve() {
    for (int i = 1; i <= n; i++) pay[i] = 100;  // 每位员工奖金最少 100 元

    queue<int> q;             // Kahn 队列：所有入度为 0 的点（没有更低的人要超过）
    for (int i = 1; i <= n; i++) {
        if (indeg[i] == 0) q.push(i);
    }

    int done = 0;             // 已经定薪出队的员工数
    while (!q.empty()) {
        int u = q.front(); q.pop();
        done++;
        // u 已经定薪，把后继端点 v 抬到 max(pay[v], pay[u] + 1)
        for (int e = head[u]; e != 0; e = nxt[e]) {
            int v = to[e];
            if (pay[u] + 1 > pay[v]) pay[v] = pay[u] + 1;
            indeg[v]--;
            if (indeg[v] == 0) q.push(v);
        }
    }

    if (done < n) {           // 还有人没轮到：约束成环，互相矛盾，无解
        cout << "Poor Xed";
    }
    else {
        ll total = 0;
        for (int i = 1; i <= n; i++) total += pay[i];
        cout << total;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();
    solve();

    return 0;
}

目录

题目描述

思路

参考代码