```pascal
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
const int S=1000005,MS=500005;
int n,s,t;
int oud[MS];
vector<int> ins[MS],ous[MS];
bool vis[MS];
int esum,to[S],c[S],nxt[S],h[MS];
int dep[MS];
inline void init()
{
esum=1;
memset(h,0,sizeof(h));
s=0;
t=500000;
}
inline void add(int x,int y,int w)
{
to[++esum]=y;
c[esum]=w;
nxt[esum]=h[x];
h[x]=esum;
}
inline bool bfs()
{
memset(dep,0,sizeof(dep));
queue<int> q;
q.push(s);
dep[s]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=h[u];i;i=nxt[i])
{
int v=to[i];
if(c[i]>0&&dep[v]==0)
{
dep[v]=dep[u]+1;
q.push(v);
}
}
}
return dep[t]>0;
}
int dfs(int u,int w)
{
if(u==t)
{
return w;
}
int sum=0;
for(int i=h[u];i;i=nxt[i])
{
int v=to[i];
if(c[i]>0&&dep[v]==dep[u]+1)
{
int re=dfs(v,min(w,c[i]));
c[i]-=re;
c[i^1]+=re;
w-=re;
sum+=re;
if(w==0)
{
break;
}
}
}
if(sum==0)
{
dep[u]=0;
}
return sum;
}
inline int dinic()
{
int ans=0;
while(bfs())
{
ans+=dfs(s,1e8);
}
return ans;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int k;
scanf("%d",&k);
while(k--)
{
int x;
scanf("%d",&x);
oud[i]++;
ins[x].push_back(i);
}
}
init();
int tot=0;
queue<int> q;
for(int i=1;i<=n;i++)
{
if(oud[i]==0)
{
q.push(i);
}
}
while(!q.empty())
{
int u=q.front();
q.pop();
for(int fa:ins[u])
{
tot++;
add(s,tot,1);
add(tot,s,0);
add(202202+tot,t,1);
add(t,202202+tot,0);
ous[fa].push_back(tot);
for(int v:ous[u])
{
add(tot,202202+v,1);
add(202202+v,tot,0);
}
if(!vis[fa])
{
vis[fa]=true;
q.push(fa);
}
}
}
printf("%d\n",tot-dinic());
return 0;
}
```
by lovely_ckj @ 2022-03-06 10:53:48
upd
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
const int S=1000005,MS=500005;
int n,s,t;
int oud[MS];
vector<int> ins[MS],ous[MS];
bool vis[MS];
int esum,to[S],c[S],nxt[S],h[MS];
int dep[MS];
inline void init()
{
esum=1;
memset(h,0,sizeof(h));
s=0;
t=500000;
}
inline void add(int x,int y,int w)
{
to[++esum]=y;
c[esum]=w;
nxt[esum]=h[x];
h[x]=esum;
}
inline bool bfs()
{
memset(dep,0,sizeof(dep));
queue<int> q;
q.push(s);
dep[s]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=h[u];i;i=nxt[i])
{
int v=to[i];
if(c[i]>0&&dep[v]==0)
{
dep[v]=dep[u]+1;
q.push(v);
}
}
}
return dep[t]>0;
}
int dfs(int u,int w)
{
if(u==t)
{
return w;
}
int sum=0;
for(int i=h[u];i;i=nxt[i])
{
int v=to[i];
if(c[i]>0&&dep[v]==dep[u]+1)
{
int re=dfs(v,min(w,c[i]));
c[i]-=re;
c[i^1]+=re;
w-=re;
sum+=re;
if(w==0)
{
break;
}
}
}
if(sum==0)
{
dep[u]=0;
}
return sum;
}
inline int dinic()
{
int ans=0;
while(bfs())
{
ans+=dfs(s,1e8);
}
return ans;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int k;
scanf("%d",&k);
while(k--)
{
int x;
scanf("%d",&x);
oud[i]++;
ins[x].push_back(i);
}
}
init();
int tot=0;
queue<int> q;
for(int i=1;i<=n;i++)
{
if(oud[i]==0)
{
q.push(i);
}
}
while(!q.empty())
{
int u=q.front();
q.pop();
for(int fa:ins[u])
{
tot++;
add(s,tot,1);
add(tot,s,0);
add(202202+tot,t,1);
add(t,202202+tot,0);
ous[fa].push_back(tot);
for(int v:ous[u])
{
add(tot,202202+v,1);
add(202202+v,tot,0);
}
if(--oud[fa]==0)
{
q.push(fa);
}
}
if(ins[u].empty())
{
tot++;
add(s,tot,1);
add(tot,s,0);
add(202202+tot,t,1);
add(t,202202+tot,0);
for(int v:ous[u])
{
add(tot,202202+v,1);
add(202202+v,tot,0);
}
}
}
printf("%d\n",tot-dinic());
return 0;
}
```
by lovely_ckj @ 2022-03-06 11:24:12
uupd
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
const int S=1000005,MS=500005;
int n,s,t;
int oud[MS];
vector<int> ins[MS],ous[MS];
bool vis[MS];
int esum,to[S],c[S],nxt[S],h[MS];
int dep[MS];
inline void init()
{
esum=1;
memset(h,0,sizeof(h));
s=0;
t=500000;
}
inline void add(int x,int y,int w)
{
to[++esum]=y;
c[esum]=w;
nxt[esum]=h[x];
h[x]=esum;
}
inline bool bfs()
{
memset(dep,0,sizeof(dep));
queue<int> q;
q.push(s);
dep[s]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=h[u];i;i=nxt[i])
{
int v=to[i];
if(c[i]>0&&dep[v]==0)
{
dep[v]=dep[u]+1;
q.push(v);
}
}
}
return dep[t]>0;
}
int dfs(int u,int w)
{
if(u==t)
{
return w;
}
int sum=0;
for(int i=h[u];i;i=nxt[i])
{
int v=to[i];
if(c[i]>0&&dep[v]==dep[u]+1)
{
int re=dfs(v,min(w,c[i]));
c[i]-=re;
c[i^1]+=re;
w-=re;
sum+=re;
if(w==0)
{
break;
}
}
}
if(sum==0)
{
dep[u]=0;
}
return sum;
}
inline int dinic()
{
int ans=0;
while(bfs())
{
ans+=dfs(s,1e8);
}
return ans;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int k;
scanf("%d",&k);
while(k--)
{
int x;
scanf("%d",&x);
oud[i]++;
ins[x].push_back(i);
}
}
init();
int tot=0;
queue<int> q;
for(int i=1;i<=n;i++)
{
if(oud[i]==0)
{
q.push(i);
}
}
while(!q.empty())
{
int u=q.front();
q.pop();
for(int fa:ins[u])
{
tot++;
add(s,tot,1);
add(tot,s,0);
add(250000+tot,t,1);
add(t,250000+tot,0);
ous[fa].push_back(tot);
for(int v:ous[u])
{
add(tot,250000+v,1);
add(250000+v,tot,0);
}
if(--oud[fa]==0)
{
q.push(fa);
}
}
if(ins[u].empty())
{
tot++;
add(s,tot,1);
add(tot,s,0);
add(250000+tot,t,1);
add(t,250000+tot,0);
for(int v:ous[u])
{
add(tot,250000+v,1);
add(250000+v,tot,0);
}
}
}
printf("%d\n",tot-dinic());
return 0;
}
```
by lovely_ckj @ 2022-03-06 12:05:42
求 hack
by lovely_ckj @ 2022-03-06 12:05:58