Задан ориентированный граф. Ребро идущее от вершины А к вершине Б означает, что А выиграл у Б в ксго. И А считает Б раком. Но если Б выиграл в ксго у C то Б и А считают C раком. Нужно составить команду в которой необходим 1 капитан. При этом никто из участников команды не должен считать капитана раком. Сами участник могут считать друг друга раками. Цифра(в 3 столбце) 1 значит что первый выиграл у второго, цифра 2 значит что второй выиграл у первого Ниже мой код #include <iostream> #include <vector> using namespace std; vector <int> G[100010]; vector <int> Gt[100010]; vector<bool> used; vector<int> order, component, minn; int res[200000]; //int n, m, num = 1; void top(int v) { used[v] = 1; for (int i = 0; i < G[v].size(); i++) { if (used[G[v][i]] == 0) { top(G[v][i]); } } order.push_back(v); } void dfs(int v) { used[v] = 1; component.push_back(v); for (int i = 0; i < Gt[v].size(); i++) { if (used[Gt[v][i]] == 0) { dfs(Gt[v][i]); } } } int main() { int n, m, num = 1, temp, count = 0; cin >> n >> m; int aa[n][n]; int vhod[n]; for (int tt = 0; tt < n; ++tt) G[tt].resize(n); while (m--) { int a, b, kk; cin >> a >> b >> kk; a--; b--; if (kk == 1) { G[a].push_back(b); Gt[b].push_back(a); aa[a][b] = 1; } else { G[b].push_back(a); Gt[a].push_back(b); aa[b][a] = 1; } } int tt; for (int x = 0; x < n; ++x){ for (int y = 0; y < n; ++y){ tt += aa[y][x]; } vhod[x] = tt; tt = 0; } used.assign(n, false); for (int i = 0; i < n; i++) { if (used[i] == 0) top(i); } used.assign(n, false); for (int i = 0; i < n; i++) { int v = order[n - 1 - i]; if (used[v] == 0) { dfs(v); for (auto I = component.begin(); I != component.end(); I++) res[*I] = num; num++; int temp = 0; for(int y:component){ for(int x: component){ temp += aa[x][y]; //y - строка, X - столбец } if(vhod[y] - temp == 0){ minn.push_back(component.size()); } } } // minn.push_back(component.size()); } int min = minn[0]; for (int k = 0; k < minn.size(); ++k) { //cout << minn[k] << " "; if (minn[k] < min) { min = minn[k]; } } cout << min << endl; cout << n - min + 1 << endl; return 0; } C #include <iostream> #include <vector> using namespace std; vector <int> G[100010]; vector <int> Gt[100010]; vector<bool> used; vector<int> order, component, minn; int res[200000]; //int n, m, num = 1; void top(int v) { used[v] = 1; for (int i = 0; i < G[v].size(); i++) { if (used[G[v][i]] == 0) { top(G[v][i]); } } order.push_back(v); } void dfs(int v) { used[v] = 1; component.push_back(v); for (int i = 0; i < Gt[v].size(); i++) { if (used[Gt[v][i]] == 0) { dfs(Gt[v][i]); } } } int main() { int n, m, num = 1, temp, count = 0; cin >> n >> m; int aa[n][n]; int vhod[n]; for (int tt = 0; tt < n; ++tt) G[tt].resize(n); while (m--) { int a, b, kk; cin >> a >> b >> kk; a--; b--; if (kk == 1) { G[a].push_back(b); Gt[b].push_back(a); aa[a][b] = 1; } else { G[b].push_back(a); Gt[a].push_back(b); aa[b][a] = 1; } } int tt; for (int x = 0; x < n; ++x){ for (int y = 0; y < n; ++y){ tt += aa[y][x]; } vhod[x] = tt; tt = 0; } used.assign(n, false); for (int i = 0; i < n; i++) { if (used[i] == 0) top(i); } used.assign(n, false); for (int i = 0; i < n; i++) { int v = order[n - 1 - i]; if (used[v] == 0) { dfs(v); for (auto I = component.begin(); I != component.end(); I++) res[*I] = num; num++; int temp = 0; for(int y:component){ for(int x: component){ temp += aa[x][y]; //y - строка, X - столбец } if(vhod[y] - temp == 0){ minn.push_back(component.size()); } } } // minn.push_back(component.size()); } int min = minn[0]; for (int k = 0; k < minn.size(); ++k) { //cout << minn[k] << " "; if (minn[k] < min) { min = minn[k]; } } cout << min << endl; cout << n - min + 1 << endl; return 0; } И также есть 4 теста тест 1 Ввод: 4 3 1 2 1 2 3 1 3 4 1 Вывод: 4 тест 2 Ввод: 3 6 1 2 1 1 2 2 1 3 1 1 3 2 2 3 1 2 3 2 Вывод: 1 тест 3 Ввод: 9 19 1 6 1 1 7 1 2 6 1 2 7 1 1 2 1 1 2 2 3 6 1 3 7 1 4 6 1 4 7 1 5 6 1 5 7 1 3 4 1 4 5 1 5 3 1 6 8 1 6 9 1 7 8 1 7 9 1 Вывод: 8 тест 4 Ввод: 7 8 1 7 1 2 7 1 4 7 1 2 3 1 3 2 1 4 5 1 6 5 2 4 6 2 Вывод: 7
первые 2 спокойно проходит, а вот на двух других ничего не получается. Я пытался реализовать идею с тем что мы ищем минимальную компоненту сильной связности с истоком. И берем капитан как этот исток, вычитаем размер компаненты так как в ней все считают капитана раком и прибавляем всех остальных. --- Сообщение объединено с предыдущим 13 ноя 2022 #include <iostream> #include <vector> using namespace std; vector <int> G[100010]; vector <int> Gt[100010]; vector<bool> used; vector<int> order, component, minn; int res[200000]; vector<int> all; int aa[10000][10000]; int n, m, num = 1, temp, count = 0; //int n, m, num = 1; void top(int v) { used[v] = 1; for (int i = 0; i < G[v].size(); i++) { if (used[G[v][i]] == 0) { top(G[v][i]); } } order.push_back(v); } void dfs(int v) { used[v] = 1; component.push_back(v); for (int i = 0; i < Gt[v].size(); i++) { if (used[Gt[v][i]] == 0) { dfs(Gt[v][i]); } } } int main() { cin >> n >> m; // int vhod[100]; for (int tt = 0; tt < n; ++tt) G[tt].resize(n); while (m--) { int a, b, kk; cin >> a >> b >> kk; a--; b--; if (kk == 1) { G[a].push_back(b); Gt[b].push_back(a); aa[a][b] = 1; } else { G[b].push_back(a); Gt[a].push_back(b); aa[b][a] = 1; } } int tt = 0; /*for (int x = 0; x < n; ++x) { for (int y = 0; y < n; ++y) { tt += aa[y][x]; } vhod[x] = tt; tt = 0; }*/ used.assign(n, false); for (int i = 0; i < n; i++) { if (used[i] == 0) top(i); } used.assign(n, false); for (int i = 0; i < n; i++) { int v = order[n - 1 - i]; if (used[v] == 0) { dfs(v); for (auto I = component.begin(); I != component.end(); I++) res[*I] = num; num++; int temp = 0; all.push_back(component.size()); for (int y : component) { for (int x : component) { temp += aa[x][y]; //y - строка, X - столбец } for (int x = 0; x < n; ++x) { for (int y = 0; y < n; ++y) { tt += aa[y][x]; } if (tt - temp > 0) { minn.push_back(component.size()); } } } // minn.push_back(component.size()); } int min = 0; for (int k = 0; k < minn.size(); ++k) { //cout << minn[k] << " "; if (minn[k] > min) { min = minn[k]; } } int min1 = 0; for (int k = 0; k < all.size(); ++k) { cout << minn[k] << " "; if (all[k] > min1) { min1 = all[k]; } } cout << min << " " << min1 << endl; cout << n - min + 1 << endl; return 0; } } C #include <iostream> #include <vector> using namespace std; vector <int> G[100010]; vector <int> Gt[100010]; vector<bool> used; vector<int> order, component, minn; int res[200000]; vector<int> all; int aa[10000][10000]; int n, m, num = 1, temp, count = 0; //int n, m, num = 1; void top(int v) { used[v] = 1; for (int i = 0; i < G[v].size(); i++) { if (used[G[v][i]] == 0) { top(G[v][i]); } } order.push_back(v); } void dfs(int v) { used[v] = 1; component.push_back(v); for (int i = 0; i < Gt[v].size(); i++) { if (used[Gt[v][i]] == 0) { dfs(Gt[v][i]); } } } int main() { cin >> n >> m; // int vhod[100]; for (int tt = 0; tt < n; ++tt) G[tt].resize(n); while (m--) { int a, b, kk; cin >> a >> b >> kk; a--; b--; if (kk == 1) { G[a].push_back(b); Gt[b].push_back(a); aa[a][b] = 1; } else { G[b].push_back(a); Gt[a].push_back(b); aa[b][a] = 1; } } int tt = 0; /*for (int x = 0; x < n; ++x) { for (int y = 0; y < n; ++y) { tt += aa[y][x]; } vhod[x] = tt; tt = 0; }*/ used.assign(n, false); for (int i = 0; i < n; i++) { if (used[i] == 0) top(i); } used.assign(n, false); for (int i = 0; i < n; i++) { int v = order[n - 1 - i]; if (used[v] == 0) { dfs(v); for (auto I = component.begin(); I != component.end(); I++) res[*I] = num; num++; int temp = 0; all.push_back(component.size()); for (int y : component) { for (int x : component) { temp += aa[x][y]; //y - строка, X - столбец } for (int x = 0; x < n; ++x) { for (int y = 0; y < n; ++y) { tt += aa[y][x]; } if (tt - temp > 0) { minn.push_back(component.size()); } } } // minn.push_back(component.size()); } int min = 0; for (int k = 0; k < minn.size(); ++k) { //cout << minn[k] << " "; if (minn[k] > min) { min = minn[k]; } } int min1 = 0; for (int k = 0; k < all.size(); ++k) { cout << minn[k] << " "; if (all[k] > min1) { min1 = all[k]; } } cout << min << " " << min1 << endl; cout << n - min + 1 << endl; return 0; } } второй вариант кода
vtlstolyarov, капитан може проиграть кому угдно, поэтому, выбрать надо его так чтобы проиграл наименьшему кол-ву людей
impelix, всё равно не сходится - в этом примере 1 проиграл наименьшему количеству людей (нулю, то есть никому не проиграл) - почему тогда капитан 4 в ответе?