题解:最基础的最大流,按照主飞行员与起点建边,副飞行员与终点建边,可以同坐的主副飞行员之间建边,值均为一,然后跑一边最大流就完美了!
代码如下:
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std; int head[],next[],v[],w[],deep[];
int s,t,cnt; void init()
{
cnt=-;
memset(head,-,sizeof(head));
memset(next,-,sizeof(next));
} void add(int from,int to,int cost)
{
cnt++;
next[cnt]=head[from];
v[cnt]=to;
w[cnt]=cost;
head[from]=cnt;
} void add_edge(int from,int to,int cost)
{
add(from,to,cost);
add(to,from,);
} int bfs(int s,int t)
{
queue<int> q;
memset(deep,,sizeof(deep));
deep[s]=;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i!=-;i=next[i])
{
if(w[i]>&&(!deep[v[i]]))
{
deep[v[i]]=deep[u]+;
q.push(v[i]);
}
}
}
if(!deep[t])
{
return ;
}
return ;
} int dfs(int u,int t,int dist)
{
if(u==t)
{
return dist;
}
for(int i=head[u];i!=-;i=next[i])
{
if((deep[v[i]]==deep[u]+)&&w[i])
{
int di=dfs(v[i],t,min(w[i],dist));
if(di>)
{
w[i]-=di;
w[i^]+=di;
return di;
}
}
}
return ;
} int dinic(int s,int t)
{
int res=;
while(bfs(s,t))
{
while(int d=dfs(s,t,inf))
{
res+=d;
}
}
return res;
} int main()
{
int n,m;
init();
scanf("%d%d",&n,&m);
s=;t=n+;
for(int i=;i<=m;i++)
{
add_edge(s,i,);
}
for(int i=m+;i<=n;i++)
{
add_edge(i,t,);
}
int x,y;
while(scanf("%d%d",&x,&y)!=EOF)
{
add_edge(x,y,);
}
int ans=dinic(s,t);
printf("%d\n",ans);
}