# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1169348 | adkjt | Bosses (BOI16_bosses) | C11 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
bool vis[5555];
vector<int> g[5555],boss[5555];
queue<int> qu;
int sum=0;
int runtree(int now)
{
int empcnt=0;
for(auto x:boss[now])
{
empcnt+=runtree(x);
}
//cout<<empcnt+1<<'\n';
sum+=empcnt+1;
return empcnt+1;
}
int main()
{
int n;
cin>>n;
for(int i=1; i<=n; i++)
{
int k;
cin>>k;
for(int j=1; j<=k; j++)
{
int x;
cin>>x;
g[x].push_back(i);
}
}
int ans=1e9;
for(int i=1; i<=n; i++)
{
int entrycnt=0;
for(int j=1; j<=n; j++) vis[j]=0,boss[j].clear();
vis[i]=1;
qu.push(i);
while(!qu.empty())
{
int now=qu.front();
qu.pop();
entrycnt++;
for(auto x:g[now])
{
if(vis[x]) continue;
qu.push(x);
boss[now].push_back(x);
vis[x]=1;
//cout<<"w"<<now<<' '<<x<<'\n';
}
}
//cout<<entrycnt<<' ';
if(entrycnt==n)
{
sum=0;
runtree(i);
ans=min(ans,sum);
}
//cout<<ans<<'\n';
}
cout<<ans;
}