先占个板子，有空再来写注释
题目
#include <stdio.h> #include <iostream> #include <string.h> #include <queue> using namespace std; const int maxn=4e2+5; const int inf=0x3f3f3f3f; struct ac { int v,c,nex; }edge[maxn << 7]; int s,e; int head[maxn],dis[maxn],curedge[maxn],cnt; void init() { cnt=0; memset(head,-1,sizeof(head)); } void addedge(int u,int v,int c) { edge[cnt]={v,c,head[u]}; head[u]=cnt++; edge[cnt]={u,0,head[v]}; head[v]=cnt++; } bool bfs() { queue<int> que; que.push(s); memset(dis,0,sizeof(dis)); dis[s]=1; while(!que.empty()) { int u=que.front(); que.pop(); for(int i=head[u];i!=-1;i=edge[i].nex) { int v=edge[i].v; int c=edge[i].c; if(dis[v]||c==0) { continue; } dis[v]=dis[u]+1; que.push(v); } } return dis[e]>0; } int dfs(int u,int flow) { if(u==e||flow==0) { return flow; } for(int &i=curedge[u];i!=-1;i=edge[i].nex) { int v=edge[i].v; int c=edge[i].c; if(dis[v]!=dis[u]+1||c==0) { continue; } int d=dfs(v,min(flow,c)); if(d>0) { edge[i].c-=d; edge[i^1].c+=d; return d; } } dis[u]=-1; return 0; } int dinic() { int sum=0,d; while(bfs()) { for(int i=0;i<=e;++i) { curedge[i]=head[i]; } while((d=dfs(s,inf))>0) { sum+=d; } } return sum; } int main() { ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); int N,F,D; cin >> N >> F >> D; s=0,e=N+N+F+D+1; init(); for(int i=1;i<=N;++i) { int f,d,t; cin >> f >> d; for(int j=0;j<f;++j) { cin >> t; addedge(t,i+F,inf); } for(int j=0;j<d;++j) { cin >> t; addedge(i+F+N,t+F+N+N,inf); } } for(int i=1;i<=N;++i) { addedge(i+F,i+F+N,1); } for(int i=1;i<=F;++i) { addedge(s,i,1); } for(int i=1;i<=D;++i) { addedge(F+N+N+i,e,1); } cout << dinic() << endl; return 0; }
