1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
| #include<bits/stdc++.h>
#define maxn 6000
using namespace std;
struct eee{
int to;
int w;
int next;
}e[maxn*3000];
int root[maxn],cnt=1,dep[maxn];
int n,m,q,x,y;
queue<int>que;
int rd() {
int x = 0, w = 1;
char ch = 0;
while (ch < '0' || ch > '9') {
if (ch == '-') w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + (ch - '0');
ch = getchar();
}
return x * w;
}
inline void add(int x,int y,int w){
e[++cnt]={y,w,root[x]};
root[x]=cnt;
}
bool bfs(){
while(que.size())que.pop();
memset(dep,0,sizeof(dep));
dep[0]=1;
que.push(0);
while(que.size()){
int u=que.front();
que.pop();
for(int i=root[u];i;i=e[i].next){
int w=e[i].w,v=e[i].to;
if(!w||dep[v])continue;
dep[v]=dep[u]+1;
que.push(v);
}
}
return dep[2*n+1];
}
int Dinic(int u,int in){
if(u==2*n+1)return in;
int ans=0;
for(int i=root[u];i;i=e[i].next){
int v=e[i].to,w=e[i].w;
if(dep[v]>dep[u]&&w){
int res=Dinic(v,min(in,w));
e[i].w-=res;
e[i^1].w+=res;
in-=res;
ans+=res;
if(!in)return ans;
}
}
if(ans==0)dep[u]=0;
return ans;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
n=rd();
m=rd();
q=rd();
while(m--){
x=rd();
add(0,x,1);
add(x,0,0);
}
for(int i=1;i<=n;i++){
add(i,i+n,1);
add(i+n,i,0);
x=rd();
while(x--){
y=rd();
add(i+n,y,1);
add(y,i+n,0);
}
}
while(q--){
x=rd();
add(x+n,2*n+1,1);
add(2*n+1,x+n,0);
}
int ans=0;
while(bfs()){
ans+=Dinic(0,0x7fffffff);
}
cout<<ans<<endl;
return 0;
}
|
