题目：
飞行大队有若干个来自各地的驾驶员，专门驾驶一种型号的飞机，这种飞机每架有两个驾驶员，需一个正驾驶员和一个副驾驶员。由于种种原因，例如相互配合的问题，有些驾驶员不能在同一架飞机上飞行，问如何搭配驾驶员才能使出航的飞机最多。
因为驾驶工作分工严格,两个正驾驶员或两个副驾驶员都不能同机飞行。
输入格式:
第一行，两个整数 n 与 m，表示共有 n 个飞行员，其中有 m 名飞行员是正驾驶员。 下面有若干行，每行有 2 个数字a,b。表示正驾驶员 a 和副驾驶员 b 可以同机飞行。
注：正驾驶员的编号在前，即正驾驶员的编号小于副驾驶员的编号。
数据保证有 2≤n≤100
输出格式:
仅一行一个整数，表示最大起飞的飞机数。
链接: https://loj.ac/problem/6000
思路：
正驾驶员与超级源点S连边，副驾驶员与超级汇点连边，最大流等于二分图最大匹配，然后a,b连边求最大流
代码：
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> using namespace std; const int MAXN=2e5+5; const int INF=0x7fffffff; typedef long long ll; int head[MAXN],tot,s,t; struct node { int to,nxt,flow; }e[MAXN]; void add(int x,int y,int z) { e[tot].to=y;e[tot].flow=z;e[tot].nxt=head[x];head[x]=tot++; } void add_edge(int x,int y,int z) { add(x,y,z);add(y,x,0); } int dep[MAXN],l,r,q[MAXN]; bool bfs() { memset(dep,0,sizeof(dep)); l=0,r=0; q[++r]=s;dep[s]=1; while(l!=r) { int u=q[++l]; for(int i=head[u];~i;i=e[i].nxt) { int v=e[i].to; if(!dep[v]&&e[i].flow) { dep[v]=dep[u]+1; q[++r]=v; } } } return dep[t]; } int dfs(int u,int min_f) { if(u==t) return min_f; int temp_f=0; for(int i=head[u];~i&&min_f;i=e[i].nxt) { int v=e[i].to; if(dep[v]==dep[u]+1&&e[i].flow) { int d=dfs(v,min(min_f,e[i].flow)); if(d>0) { min_f-=d; temp_f+=d; e[i].flow-=d; e[i^1].flow+=d; } } } if(!temp_f)dep[u]=-1; return temp_f; } int dinic() { int res=0; while(bfs()) res+=dfs(s,INF); return res; } int main() { int n,m;scanf("%d%d",&n,&m); s=0,t=n+1; memset(head,-1,sizeof(head)); for(int i=1;i<=m;i++) add_edge(s,i,1); for(int i=m+1;i<=n;i++) add_edge(i,t,1); int x,y; while(scanf("%d%d",&x,&y)!=EOF) { add_edge(x,y,1); } int ans=dinic(); printf("%d ",ans); return 0; }