这道题是因为模拟测想了个沙雕算法，然后炸了。
但是算法感觉还是可以康康的。就编了道题自嗨。qaq
顺便数据是用标程编的，如果被HACK辽望留言指正。
大概就是用树状数组或线段树优化图的建边。让空间复杂度从(nm)降到 (nlog_2{n}),时间复杂度也会相应降许多。
就没了……
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
#define inf 1000000009
struct node{
int next,to,val;
}e[360050];
int n,m,k,cnt=1,maxflow,start,towhere;
int head[40050],late[40050],dis[40050];
int tree[40050];
queue<int> q;
void add(int from,int to,int val){
e[++cnt].next=head[from];
e[cnt].to=to;
e[cnt].val=val;
head[from]=cnt;
}
int lowbit(int o){
return o&(-o);
}
void build(){
for(int i=1;i<=m;i++){
add(i,towhere,1);
add(towhere,i,0);
int x=i+lowbit(i);
if(x <= m){
add(x,i,lowbit(i));
add(i,x,0);
}
}
}
void query(int o,int x){
// printf("%d %d
",o,x-m-k);
while(o>=1){
add(x,o,1);
add(o,x,0);
o-=lowbit(o);
}
}
/*
start 0
k m+1~m+k
m 1~m
n m+k+1~m+k+n
n` m+k+n+1~m+k+n+n
towhere m+k+2n+1
*/
void cls(){
for(int i=0;i<=towhere;i++){
dis[i]=inf;
late[i]=head[i];
}
dis[start]=0;
queue<int> empty;
swap(empty,q);
}
bool bfs(int st,int to){
cls();
q.push(st);
while(!q.empty()){
int o=q.front();
q.pop();
for(int i=head[o];i!=0;i=e[i].next){
int x=e[i].to;
if(e[i].val>0 && dis[x]>dis[o]+1){
dis[x]=dis[o]+1;
q.push(x);
}
}
}
return dis[to]<inf;
}
int dfs(int o,int limit){
if(limit==0 || o==towhere) return limit;
int flow=0;
for(int i=late[o];i!=0;i=e[i].next){
late[o]=i;
int x=e[i].to;
if(dis[x]==dis[o]+1){
int water=dfs(x,min(limit,e[i].val));
limit-=water;
flow+=water;
e[i].val-=water;
e[i^1].val+=water;
}
if(limit==0) break;
}
return flow;
}
void dinic(int st,int to){
while(bfs(st,to)){
maxflow+=dfs(st,inf);
}
}
int main()
{
// freopen("date.in","r",stdin);
// freopen("ans.out","w",stdout);
scanf("%d %d %d",&k,&n,&m);
towhere=m+2*n+k+1;
for(int i=1;i<=k;i++){
int j=0;
while(1){
int tp;
scanf("%d",&tp);
if(tp==0) break;
j++;
add(m+i,m+n+k+tp,1);
add(m+n+k+tp,m+i,0);
}
add(start,m+i,j);
add(m+i,start,0);
}
for(int i=1;i<=n;i++){
add(m+n+k+i,m+k+i,1);
add(m+k+i,m+n+k+i,0);
}
build();
for(int i=1;i<=n;i++){
// printf("%d %d %d
",i,n,cnt);
int tp;
scanf("%d",&tp);
query(tp,m+k+i);
}
dinic(start,towhere);
printf("%d",maxflow);
return 0;
}
//by jmh_
by thorn_