| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1185589 | GoBananas69 | Bosses (BOI16_bosses) | C++20 | 0 ms | 0 KiB |
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const long long MOD = 1000000007;
const int maxn = 505;
const int Lg = 23;
const long long inf = 1000000000;
typedef long long ll;
typedef pair<ll, ll> pair<int, int>;
vector<ll> g[maxn], c[maxn];
bool use[maxn];
ll cu = 0;
ll dfs(int v, int p = -1) {
ll x = 0;
for (int to : c[v]) {
if (to == p)
continue;
x += dfs(to, v);
}
cu += x + 1;
return x + 1;
}
void solve() {
int n;
cin >> n;
pair<int, int> mb = {-inf, -inf};
for (int i = 1; i <= n; i++) {
int k;
cin >> k;
for (int j = 0; j < k; j++) {
int p;
cin >> p;
g[p].push_back(i);
mb = max(mb, make_pair((ll)g[p].size(), (ll)p));
}
}
ll ans = inf;
for (int i = 1; i <= n; i++) {
if (g[i].empty())
continue;
if (abs((int)g[i].size() - (int)mb.first) > 1)
continue;
for (int j = 1; j <= n; j++)
c[j].clear();
queue<int> q;
q.push(i);
memset(use, 0, sizeof(use));
use[i] = true;
int h = 1;
while (!q.empty()) {
int v = q.front();
q.pop();
for (auto to : g[v]) {
if (use[to])
continue;
c[v].push_back(to);
q.push(to);
use[to] = true;
h++;
}
}
if (h == n) {
cu = 0;
dfs(i);
ans = min(ans, cu);
}
}
cout << ans << "\n";
}
int main() {
cin.tie(0) -> sync_with_stdio(0);
int tt = 1;
while (tt--) {
solve();
}
return 0;
}