使用贪心算法实现奖金分配的问题案例项目源码

题目描述

你是公司的董事长，也就是公司里最懂事的人。今年业绩大丰收，要给n名员工发放奖金，编号从1到n。但是在员工之间有着互相攀比奖金的不良风气。有m条注意事项你要小心，第i条要求是，不能够出现Ai比Bi少拿超过Ci元，换句话讲，Bi哪怕比Ai多拿，差距也不能超过Ci元。这些要求必须都满足，不然就会有人不满意奖金分配而辞职，你的分配方案不能让任何人辞职。

1号员工就是你自己，2号员工是你的儿子，你希望给儿子的奖金越多越好，请问你儿子奖金超过你自己的奖金最多可以是多少？保证答案有限。

输入输出格式

输入格式
输入文件bonus.in
第一行为正整数n和m，n<=50000，m<=200000。之后行共m行，每行三个整数ai,bi和ci。1<=ai,bi<=n，0<=ci<=1000。
输出格式
输出文件bonus.out 输出一个整数。

输入输出样例

输入样例
2 2
1 2 9
2 1 8
输出样例
9

实现代码

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 50000;
const int MAXM = 200000;

struct Bonus {
    int a, b, c;
} bonuses[MAXM];

bool cmp(Bonus b1, Bonus b2) {
    return b1.c > b2.c;  // 按照 c 从大到小排序
}

int fa[MAXN + 1];  // 并查集数组

int find(int x) {  // 并查集查找根节点
    if (fa[x] == x) {
        return x;
    } else {
        return fa[x] = find(fa[x]);
    }
}

bool merge(int x, int y) {  // 并查集合并两个集合
    int fx = find(x);
    int fy = find(y);
    if (fx == fy) {
        return false;
    } else {
        fa[fx] = fy;
        return true;
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        cin >> bonuses[i].a >> bonuses[i].b >> bonuses[i].c;
    }

    sort(bonuses, bonuses + m, cmp);

    for (int i = 1; i <= n; i++) {
        fa[i] = i;  // 初始化并查集
    }

    int max_bonus = 0;
    for (int i = 0; i < m; i++) {
        if (merge(bonuses[i].a, bonuses[i].b)) {  // 如果合并两个集合成功
            max_bonus = bonuses[i].c;  // 更新最大奖金
            if (find(1) == find(2)) {  // 如果 1 号员工和 2 号员工在同一个集合中，说明儿子的奖金已经超过了自己的奖金
                break;
            }
        }
    }

    cout << max_bonus << endl;

    return 0;
}

程序先读入奖金分配规则（注意事项），按照 c 从大到小排序。然后初始化并查集数组，从最大的 c 开始遍历规则，如果 a 和 b 不在同一个集合中，则合并两个集合，并更新最大的 c。如果 1 号员工和 2 号员工在同一个集合中，说明儿子的奖金已经超过了自己的奖金，可以结束遍历。

运行截图