Матч 407, Зарплата в корпорации (CorporationSalary)

Дивизион 2, Уровень 2; Дивизион 1, Уровень 1

Вы работаете менеджером в большой корпорации. Каждый работник имеет несколько прямых менеджеров и несколько непосредственных подчиненных. Будем говорить, что X является боссом Y, если существует такая последовательность работников A, B , …, D, что X является менеджером A, A является менеджером B и так далее, а D является менеджером Y (если X является прямым менеджером Y, то X является боссом Y). Если X является боссом Y, то Y не является боссом X. Зарплата работника, не имеющего подчиненных, равна 1. Иначе зарплата работника равна сумме зарплат всех его подчиненных.

Массив relations описывает отношение “менеджер/подчиненный”. Если relations[i][j] = ‘Y’, то i - ый работник является прямым менеджером j - ого работника. Иначе relations[i][j] = ‘N’. Найти сумму зарплат всех работников.

Класс: CorporationSalary

Метод: long totalSalary(vector<string> relations)

Ограничения: relations содержит от 1 до 50 элементов, все элементы relations[i] содержат одинаковое количество букв ‘Y’ или ‘N’.

Вход. Массив relations, описывающий отношения между работниками.

Выход. Сумма зарплат всех работников.

Пример входа

relations

{"N"}

{"NNYN",

"NNYN",

"NNNN",

"NYYN"}

{"NNNNNN",

"YNYNNY",

"YNNNNY",

"NNNNNN",

"YNYNNN",

"YNNYNN"}

Пример выхода

1

5

17

РЕШЕНИЕ

графы – поиск в глубину

Массив relations задает матрицу смежности ориентированного графа. Совершим топологическую сортировку вершин графа. Функция dfs(i) вычисляет зарплату i -го работника, и сохраняет ее в ячейке salary[i]. Сумма зарплат всех работников равна сумме элементов массива salary.

ПРОГРАММА

#include <cstdio>

#include <string>

#include <vector>

#include <memory>

#include <numeric>

using namespace std;

long long salary[50];

vector<string> rel;

long long dfs(int i)

{

int j;

long long &res = salary[i];

if (salary[i] > 0) return salary[i];

for(res = j = 0; j < rel.size(); j++)

if (rel[i][j] == 'Y') res += dfs(j);

if (!res) res = 1;

return res;

}

class CorporationSalary

{

public:

long long totalSalary(vector<string> relations)

{

memset(salary,0,sizeof(salary)); rel = relations;

for(int i = 0; i < relations.size(); i++)

if (!salary[i]) dfs(i);

return accumulate(salary,salary + relations.size(),(long long)0);

}

};