Cómo implementar este problema: Problema – C – Fuerzas de código

Creo que la idea clave en este problema es darse cuenta de que después de realizar tareas en la computadora 1, nunca nos movemos directamente a la computadora 3 porque pasar de 1 a 2 (costo 1) y luego de 2 a 3 (costo 1) tiene el mismo costo como pasar de 1 a 3.
Entonces, desde la computadora 1, siempre pasamos a la computadora 2. De 2 a 3, y de 3 a 1.

Por lo tanto, podemos simular el juego comenzando en las computadoras 1, 2 y 3, y generar el mínimo de las tres simulaciones.

Una tarea puede completarse si todas las tareas de las que depende ya se completaron. Esto es lo mismo que el tipo topológico.

• ¿Qué es mejor en C #, mantener una variable con un tamaño de matriz o llamar a la longitud de la matriz?
• ¿Cómo se determina la longitud de una matriz en C?
• ¿Cómo ordenar un millón de números en tiempo de registro usando la solución Norman Hardy?
• La inmutabilidad es primordial en la mayoría de los dominios de FP, pero ¿hacen copias superficiales o profundas?
• Cómo implementar la codificación y decodificación de Huffman usando una matriz y no un árbol

Aquí hay una implementación de muestra en C ++ y un par de comentarios.

#include
#include
#include
#include
using namespace std;
const int MAX = 200 + 1;
int move_to[4] = {0, 2, 3, 1};
int computer[MAX], in_degree[MAX], n;
vector precedes[MAX]; // Simulate the game starting at computer 'start_at'.
int Simulate(int start_at) {
vector available[4];
int i, num_done = 0, cost = 0, cur = start_at, num_processed[4] = {0,0,0,0}, degree[MAX];
memcpy(degree, in_degree, sizeof degree);
// Check what tasks do not have any dependencies and add them to the available lists.
for (i = 1; i <= n; i++)
if (degree[i] == 0)
available[computer[i]].push_back(i); for (;;) {
for (; num_processed[cur] < (int)available[cur].size(); num_processed[cur]++) {
int task = available[cur][num_processed[cur]];
cost++;
num_done++;
// Process this task. Decrease the number of depencies of task that require this one.
// If the number of dependencies becomes 0, then the task can be done.
for (auto j : precedes[task]) {
if (--degree[j] == 0)
available[computer[j]].push_back(j);
}
}
if (num_done == n)
return cost;
cost++;
cur = move_to[cur];
}
return -1;
} int main() {
int i, j, k, res;
cin >> n;
for (i = 1; i <= n; i++)
cin >> computer[i];
for (i = 1; i <= n; i++) {
cin >> in_degree[i];
for (k = 0; k < in_degree[i]; k++) {
cin >> j;
precedes[j].push_back(i);
}
}
res = min(Simulate(1), Simulate(2));
res = min(res, Simulate(3));
printf("%d\n", res);
return 0;
}

#include
#include
#include
#include
using namespace std;
const int MAX = 200 + 1;
int move_to[4] = {0, 2, 3, 1};
int computer[MAX], in_degree[MAX], n;
vector precedes[MAX]; // Simulate the game starting at computer 'start_at'.
int Simulate(int start_at) {
vector available[4];
int i, num_done = 0, cost = 0, cur = start_at, num_processed[4] = {0,0,0,0}, degree[MAX];
memcpy(degree, in_degree, sizeof degree);
// Check what tasks do not have any dependencies and add them to the available lists.
for (i = 1; i <= n; i++)
if (degree[i] == 0)
available[computer[i]].push_back(i); for (;;) {
for (; num_processed[cur] < (int)available[cur].size(); num_processed[cur]++) {
int task = available[cur][num_processed[cur]];
cost++;
num_done++;
// Process this task. Decrease the number of depencies of task that require this one.
// If the number of dependencies becomes 0, then the task can be done.
for (auto j : precedes[task]) {
if (--degree[j] == 0)
available[computer[j]].push_back(j);
}
}
if (num_done == n)
return cost;
cost++;
cur = move_to[cur];
}
return -1;
} int main() {
int i, j, k, res;
cin >> n;
for (i = 1; i <= n; i++)
cin >> computer[i];
for (i = 1; i <= n; i++) {
cin >> in_degree[i];
for (k = 0; k < in_degree[i]; k++) {
cin >> j;
precedes[j].push_back(i);
}
}
res = min(Simulate(1), Simulate(2));
res = min(res, Simulate(3));
printf("%d\n", res);
return 0;
}

#include
#include
#include
#include
using namespace std;
const int MAX = 200 + 1;
int move_to[4] = {0, 2, 3, 1};
int computer[MAX], in_degree[MAX], n;
vector precedes[MAX]; // Simulate the game starting at computer 'start_at'.
int Simulate(int start_at) {
vector available[4];
int i, num_done = 0, cost = 0, cur = start_at, num_processed[4] = {0,0,0,0}, degree[MAX];
memcpy(degree, in_degree, sizeof degree);
// Check what tasks do not have any dependencies and add them to the available lists.
for (i = 1; i <= n; i++)
if (degree[i] == 0)
available[computer[i]].push_back(i); for (;;) {
for (; num_processed[cur] < (int)available[cur].size(); num_processed[cur]++) {
int task = available[cur][num_processed[cur]];
cost++;
num_done++;
// Process this task. Decrease the number of depencies of task that require this one.
// If the number of dependencies becomes 0, then the task can be done.
for (auto j : precedes[task]) {
if (--degree[j] == 0)
available[computer[j]].push_back(j);
}
}
if (num_done == n)
return cost;
cost++;
cur = move_to[cur];
}
return -1;
} int main() {
int i, j, k, res;
cin >> n;
for (i = 1; i <= n; i++)
cin >> computer[i];
for (i = 1; i <= n; i++) {
cin >> in_degree[i];
for (k = 0; k < in_degree[i]; k++) {
cin >> j;
precedes[j].push_back(i);
}
}
res = min(Simulate(1), Simulate(2));
res = min(res, Simulate(3));
printf("%d\n", res);
return 0;
}

#include
#include
#include
#include
using namespace std;
const int MAX = 200 + 1;
int move_to[4] = {0, 2, 3, 1};
int computer[MAX], in_degree[MAX], n;
vector precedes[MAX]; // Simulate the game starting at computer 'start_at'.
int Simulate(int start_at) {
vector available[4];
int i, num_done = 0, cost = 0, cur = start_at, num_processed[4] = {0,0,0,0}, degree[MAX];
memcpy(degree, in_degree, sizeof degree);
// Check what tasks do not have any dependencies and add them to the available lists.
for (i = 1; i <= n; i++)
if (degree[i] == 0)
available[computer[i]].push_back(i); for (;;) {
for (; num_processed[cur] < (int)available[cur].size(); num_processed[cur]++) {
int task = available[cur][num_processed[cur]];
cost++;
num_done++;
// Process this task. Decrease the number of depencies of task that require this one.
// If the number of dependencies becomes 0, then the task can be done.
for (auto j : precedes[task]) {
if (--degree[j] == 0)
available[computer[j]].push_back(j);
}
}
if (num_done == n)
return cost;
cost++;
cur = move_to[cur];
}
return -1;
} int main() {
int i, j, k, res;
cin >> n;
for (i = 1; i <= n; i++)
cin >> computer[i];
for (i = 1; i <= n; i++) {
cin >> in_degree[i];
for (k = 0; k < in_degree[i]; k++) {
cin >> j;
precedes[j].push_back(i);
}
}
res = min(Simulate(1), Simulate(2));
res = min(res, Simulate(3));
printf("%d\n", res);
return 0;
}