Here is the condition, you need the optimal solution of the problem! alt text

My solution passes 19 tests out of 20. I can give the code if needed. Tests also have everything, I can throw. I know my mistake and I know how to fix it, but if I correct it, the complexity will increase in the order of n !, which will not be permissible in this case. The general algorithm looks like this:

0) считываю граф и переориентирую его 1) выбираю все вершины истоки(вершины в которые не входит ни одно ребро) 2) запускаю dfs от каждого истока, запуск - dfs(int x, int day) - для истока day = 0 2.1) проверяю на наличие цикла 2.2) в массив для каждой вершину записываю самый длинный путь = day 2.3) для смежной, закрытой, не помеченной вершины, запуск-dfs(v[x][i], day + 1) 3) Если есть цикл то вывожу -1 и выхожу 4) иначе произвожу подсчет дней. Вот здесь и возникает ошибка, допустим входные данные 4 2 тогда моя программа распределит вершины в след. порядке 0 1 день - 1 2 0 2 день - 3 0 3 день - 4 1 3 хотя можно управиться и за 2 дня т.е. важен порядок выбора вершин с одинаковым приоритетом. Получается нужна перебирать набор вершин и подсчитывать кол-во дней для каждой новой генерации и выбирать минимум, что я не в состоянии сделать из - за ограничения времени 

Here is the code:

 #include <iostream> #include <cstdio> #include <vector> #define N 20 using namespace std; typedef vector<int> graph; vector<graph> v(N), g(N); int n, m, col[N], days[N]; bool used[N], f = true, istok[N], used2[N]; void dfs ( int x, int day ) { days[x] = day; used[x] = true; col[x] = 1; // open vertex for (int i = 0; i < v[x].size(); i++) if ( !used[v[x][i]] ) dfs(v[x][i], day + 1); else if ( col[v[x][i]] == 1 ) // Cycle { f = false; return; } else if ( day + 1 > days[v[x][i]] ) // new way is longer than old one dfs(v[x][i], day + 1); col[x] = 2; // close vertex } bool good ( int x ) { for (int i = 0; i < g[x].size(); i++) if ( !used[g[x][i]] ) return false; return !used[x]; } int main() { freopen("a.in", "r", stdin); freopen("a.out", "w", stdout); //vvod & init int k, x, l = 0; cin >> n >> m; for (int i = 0; i < n; i++) { cin >> k; if ( k == 0 ) istok[i] = true; // array of sources for (int j = 0; j < k; j++) { cin >> x; x--; v[x].push_back(i); g[i].push_back(x); } used[i] = false; } //solve for (int i = 0; i < n; i++) if ( istok[i] ) dfs(i, 0); for (int i = 0; i < n; i++) { if ( !used[i] ) f = false; used[i] = false; used2[i] = false; } //output if ( !f ) { cout << -1; return 0; } int s = 0, day = 0; f = true; while (f) { f = false; x = 0; for (int j = 0; j < n; j++) if ( days[j] <= day && x < m && good(j) ) { used2[j] = true; f = true; x++; } for (int j = 0; j < n; j++) used[j] = used2[j]; day++; } cout << day - 1; return 0; } 
  • Something your description of the algorithm in the 4th paragraph does not converge with the code. The program will find the maximum route = 2 days, as expected. - KaZaca
  • No, she will return 3 days ..! because in the for loop (int j = 0; j <n; j ++), first there will be j = 0, j = 1 and he will choose 2 of these works! then quits the cycle, zeroes the number of completed work (x = 0), then finds a job again (j = 2), (j = 3) will not be performed because good (3) returns false, because 2 only at this stage is performed. and then on day 3 he will choose (j = 3). 3 days will turn out - Evgeny536
  • So we will not come to the result. The problem is solved by finding the maximum path in a directed graph. The search must be performed in depth and terminated when the path is exceeded or looped, otherwise it will return the maximum path. In your code, for some reason, two graphs are created and not one of them is built on the root (the additional istok array is istok ). Depth search is implemented, but many unnecessary flags are used. For example, used not needed and besides, it can lead to erroneous results. col may well take two values. - KaZaca

0