Матч
313, Параллельное программирование (ParallelProgramming)
Дивизион 2,
Уровень 3
Имеется сложная система,
состоящая из нескольких работающих параллельно процессоров. Но некоторые
процессоры могут начать работу только тогда, когда другие закончат свою работу.
i - ый элемент массива time содержит время выполнения работы i -
ым процессором (в миллисекундах). Информация о зависимости выполнения работ
содержится в массиве prec: prec[i][j] содержит ‘Y’, если процессор j может начать работу только по завершению
работы процессора i, и ‘N’, если
время работы i - го и j - го процессоров не зависят друг от
друга.
Необходимо найти наименьшее время
(в миллисекундах), за которое все процессоры выполнят свои работы. Если работы
выполнить невозможно, вернуть -1.
Класс: ParallelProgramming
Метод: int minTime(vector<int> time, vector<string>
prec)
Ограничения:
time и prec содержит одинаковое количество
элементов (от 1 до 50), 1 £ time[i] £ 1000 строк, prec[i]
содержит prec.size() символов ‘N’ или ‘Y’,prec[i][i] = ‘N’.
Вход. Массив time, содержащий время работы
процессоров и массив prec, описывающий
зависимость работы процессоров друг от друга.
Выход. Наименьшее время (в миллисекундах), необходимое для
выполнения работ всеми процессорами. Если работы выполнить невозможно, вернуть
-1.
Пример входа
|
time |
prec |
|
{150,200,250} |
{"NNN", "NNN",
"NNN"} |
|
{150,200,250} |
{"NNN", "YNN",
"NNN"} |
|
{150,200,250} |
{"NYN", "NNY",
"YNN"} |
Пример выхода
250
350
-1
РЕШЕНИЕ
топологическая сортировка
Построим
граф зависимостей работ процессоров и через поиск в глубину топологически
отсортируем их в массиве top. Если граф имеет цикл, то топологическая
сортировка невозможна, и метод minTime
возвращает -1. Граф имеет цикл, если для некоторых i и j (i < j) существует ребро (top[i],
top[j]). В массиве StartTime храним
время начала работы процессоров, в EndTime – время окончания работы. Изначально
положим StartTime[i] = 0, EndTime[i] = time[i], 0 £ i
< SIZE, где SIZE – число вершин в графе. В переменной p перебираем номера вершин в последовательности их топологической сортировки, и для каждого
ребра (p, j) устанавливаем StartTime[j]
= max(StartTime[j], EndTime[p]). Присваивание говорит о том, что j - ая работа может начаться не раньше,
чем закончится выполняться p - ая
работа. Искомое время выполнения всех работ равно максимальному значению в
массиве EndTime.
Другое решение задачи базируется
на том факте, что если функция dfs(i)
возвращает время окончания работы i -
го процессора, то при наличии ребра (j,
i) имеет место соотношение
EndTime[i] = max(EndTime[i], dfs(j) + time[i])
Оно означает, что если i -
ая работа зависит от j - ой, то время
ее окончания не меньше времени окончания j
- ой работы плюс время ее выполнения. Переменная Cycle устанавливается в 1, если в графе встречается цикл.
Изначально used[i] = 0 (i - ая вершина белая). Равенство used[i] = 1 имеет место, если i - ая вершина встречалась в графе, но
не была обработана до конца (является серой) и used[i] = 2, если i - ая
вершина полностью обработана (черная). В ориентированном графе существует цикл,
если существует ребро, ведущее в серую вершину.
ПРОГРАММА
#include <cstdio>
#include <vector>
#include <string>
#define MAX 51
using namespace std;
int m[MAX][MAX], used[MAX], top[MAX];
int SIZE, ptr;
void dfs(int i)
{
used[i] = 1;
for(int j = 0; j <
SIZE; j++)
if (m[i][j] && !used[j]) dfs(j);
top[ptr++] = i;
}
class ParallelProgramming
{
public:
int StartTime[MAX], EndTime[MAX];
int minTime(vector<int>
time, vector<string> prec)
{
int i, j, p;
SIZE = prec.size();
for(i = 0; i < SIZE; i++)
for(j = 0; j < SIZE; j++)
m[i][j] = (prec[i][j] == 'Y');
ptr = 0;
memset(used,0,sizeof(used));
for(i = 0; i < SIZE; i++)
if (!used[i]) dfs(i);
for(i = 0; i < SIZE - 1; i++)
for(j
= i + 1; j < SIZE; j++)
if (m[top[i]][top[j]]) return -1;
for(i = 0; i < SIZE; i++)
StartTime[i] = 0, EndTime[i] = time[i];
for(i = SIZE - 1; i >= 0; i--)
{
p = top[i];
EndTime[p] = StartTime[p] + time[p];
for(j = 0; j < SIZE; j++)
if (m[p][j]) StartTime[j] =
max(StartTime[j],EndTime[p]);
}
for(p = i = 0; i < SIZE; i++)
if (EndTime[i] > p) p = EndTime[i];
return p;
}
};
Реализация метода без
топологической сортировки.
#include <cstdio>
#include <vector>
#include <string>
using namespace std;
#define MAX 51
int m[MAX][MAX],used[MAX];
int Cycle,res,SIZE;
vector<int> _time,EndTime;
int max(int i, int j)
{
return (i > j) ? i
: j;
}
int dfs(int i)
{
if (used[i] == 2)
return EndTime[i];
if (used[i] == 1)
{Cycle = 1; return 0;}
used[i] = 1;
for(int
j=0;j<SIZE;j++)
if (m[j][i])
EndTime[i] = max(EndTime[i],dfs(j)+_time[i]);
used[i] = 2;
return EndTime[i];
}
class ParallelProgramming{
public:
int
minTime(vector<int> time, vector<string> prec)
{
int i,j;
SIZE = prec.size();
EndTime = _time = time;
for(i=0;i<SIZE;i++)
for(j=0;j<SIZE;j++)
m[i][j] =
(prec[i][j] == 'Y');
Cycle = res = 0;
memset(used,0,sizeof(used));
for(i=0;i<SIZE;i++)
if ((EndTime[i] =
dfs(i)) > res) res = EndTime[i];
return (Cycle) ? -1
: res;
}
};