SRM 679 Div1 Easy 250 FiringEmployees

問題

N人の人達の上司、給料、生産能力が与えられる。
この会社の利益はN人の生産能力-給料の合計値となる。
生産能力が給料よりも低い人がいるので、そのような人をリストラすることで会社の利益を最大化したいが、ある人をリストラするとその人の部下達も全員リストラしなければならない。
適切にリストラを行うことで得られる会社全体の利益の最大値を求めよ。

解法

上司と部下の関係は木構造となっている。
ある部分木の利益が負の値であるなら、そのような部分木を削ることで会社の利益を増やすことができる。
したがって、葉っぱから根に向かってトポロジカル順にそのような部分木を見つけ次第リストラしていくようにしていけば会社の利益を最大化することができる。

ソース

#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <fstream>

using namespace std;

#define MAX_N 2510

class FiringEmployees {
public:

  int N;
  int inCnt[MAX_N];
  bool used[MAX_N];
  vector<int> List;

  int memo[MAX_N];

  int fire(vector<int> manager, vector<int> salary, vector<int> productivity) {

    N = manager.size();

    int ret = 0;
    
    for(int i = 0; i < N; i++){
      manager[i]--;
      if(manager[i] < 0)
	manager[i] = N;
    }

    for(int i = 0; i < N; i++){
      ret += productivity[i] - salary[i];
    }
    
    memset(inCnt, 0, sizeof(inCnt));
    memset(used, 0, sizeof(used));

    for(int i = 0; i < N; i++){
      inCnt[manager[i]]++;
    }

    List.clear();
    
    for(int i = 0; i < N; i++){
      if(inCnt[i] == 0 && used[i] == false){
	int pos = i;
	while(true){
	  List.push_back(pos);
	  used[pos] = true;
	  if(pos == N)
	    break;
	  int nextPos = manager[pos];
	  inCnt[nextPos]--;
	  if(inCnt[nextPos] == 0 && !used[nextPos])
	    pos = nextPos;
	  else
	    break;
	}
      }
    }

    memset(memo, 0, sizeof(memo));

    for(int i = 0; i < List.size() - 1; i++){
      int pos = List[i];
      int nextPos = manager[pos];
      memo[pos] += productivity[pos] - salary[pos];
      if(memo[pos] < 0){
	ret -= memo[pos];
      }
      else{
	memo[nextPos] += memo[pos];
      }
    }
    
    return ret;

  }
};