SRM 679 Easy(250) FiringEmployees

「制約の有効活用」

問題

企業内の上司・部下の関係が木構造で与えられる。各従業員は自分よりも番号の若いいずれかの従業員の部下である。従業員ごとに利益の額が設定されている(これは正にも負にもなりうる)。さて、何人かの従業員を解雇することで企業の利益を最大化したいのだが、ある従業員を解雇するとその部下も全員解雇しなくてはならない。この制約のもとで得られる最大の利益を求めよ。

制約

従業員の数:

解法

逆順にループを回し貪欲法。木なのでdfsを使ってもよいが、「各従業員は自分よりも番号の若いいずれかの従業員の部下」という条件を使えばループを逆順に回すだけで子→親への遷移が可能。ある頂点を根とする部分木の総和Sが確定すれば、Sが正のときは親に加算する、Sが負のときは加算しない(解雇する)とすればよい。

• 解法例: C++

class FiringEmployees {
    public:
    int fire(vector<int> manager, vector<int> salary, vector<int> productivity) {
        int n = manager.size();
        vi profit(n);
        rep(i, n) profit[i] = 0;
        int ans = 0;
        rrep(i, n) {
            profit[i] += productivity[i] - salary[i];
            if (profit[i] < 0)
                continue;

            int m = manager[i] - 1;
            if (m < 0) {
                ans += profit[i];
            } else {
                profit[m] += profit[i];
            }
        }

        return ans;
    }
};