4077. Зарплата в корпорации

Вы работаете менеджером в большой корпорации. Каждый работник может иметь несколько прямых менеджеров и несколько непосредственных подчиненных. Его подчиненные, в свою очередь, также могут иметь своих подчиненных. А его прямые менеджеры могут иметь своих менеджеров. Будем говорить, что x является боссом y, если существует такая последовательность работников a, b, …, d, что x является менеджером a, a является менеджером b и так далее, а d является менеджером y (если x является прямым менеджером y, то x является боссом y). Если a является боссом b, то b не может быть боссом a. Согласно новой политике корпорации зарплата работника, не имеющего подчиненных, равна 1. Иначе зарплата работника равна сумме зарплат всех его подчиненных.

Вам заданы отношения между работниками. Необходимо найти зарплату всех работников.

Вход. Содержит несколько тестов. Первая строка каждого теста содержит количество работников n (n ≤ 50). В следующих n строках заданы отношения между работниками: j-ый символ i-ой строки равен 'Y', если работник i является прямым менеджером работника j, и 'N' иначе.

Выход. Для каждого теста вывести в отдельной строке суммарную зарплату всех работников.

Пример входа	Пример выхода
1 N 4 NNYN NNYN NNNN NYYN 6 NNNNNN YNYNNY YNNNNY NNNNNN YNYNNN YNNYNN	1 5 17

РЕШЕНИЕ

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

Анализ алгоритма

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

Пример

Графы, заданные во втором и третьем тестах, изображены ниже. Возле каждой вершины записана зарплата работника, ей соответствующая. Дуги дерева поиска в глубину изображены красным цветом.

Реализация алгоритма

Матрицу смежности графа храним в массиве rel. Зарплату i-го работника подсчитываем в ячейке salary[i].

#define MAX 51

long long salary[50];

char rel[MAX][MAX];

Функция dfs совершает поиск в глубину из вершины i – вычисление зарплаты i-го работника.

long long dfs(int i)

{

int j;

long long &res = salary[i];

Если зарплата i-го работника уже подсчитана (salary[i] ≠ 0), то завершаем поиск.

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

Иначе запускаем поиск в глубину со всех сыновей вершины i, вычисляем зарплаты всех подчиненных i-го работника. Зарплата i-го работника равна сумме зарплат всех его подчиненных.

for(res = j = 0; j < n; j++)

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

Если res = 0, то у i-го работника нет подчиненных. Устанавливаем его зарплату равной 1.

if (res == 0) res = 1;

return res;

}

Основная часть программы. Читаем в массив rel матрицу смежности графа.

while(scanf("%d\n",&n) == 1)

{

for(i = 0; i < n; i++) gets(rel[i]);

memset(salary,0,sizeof(salary));

Запускаем поиск в глубину на ориентированном графе. Находим зарплату каждого работника.

for(i = 0; i < n; i++)

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

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

for(res = i = 0; i < n; i++)

res += salary[i];

printf("%lld\n",res);

}

Java реализация

import java.util.*;

import java.io.*;

public class Main

{

static String rel[];

static long salary[];

public static long dfs(int i)

{

int j;

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

for(j = 0; j < rel.length; j++)

if (rel[i].charAt(j) == 'Y') salary[i] += dfs(j);

if (salary[i] == 0) salary[i] = 1;

return salary[i];

}

public static void main(String[] args) throws IOException

{

//Scanner con = new Scanner(new FileReader ("4077.in"));

Scanner con = new Scanner(System.in);

while(con.hasNext())

{

int n = con.nextInt();

rel = new String[n];

for(int i = 0; i < n; i++)

rel[i] = con.next();

long res = 0;

salary = new long[n];

for(int i = 0; i < n; i++)

if (salary[i] == 0) dfs(i);

for(int i = 0; i < n; i++)

res += salary[i];

System.out.println(res);

}

con.close();

}

}