先贴题面
讲真确实是水题w简单的二分图最大匹配,可以转化为网络流来做.
首先建立超级源点$s$和$t$(编号$0$和$v+1$),从超级源点向所有正飞行员连一条容量为1的边,然后对于所有可能的匹配连一条从正飞行员到副飞行员的边,最后将所有副飞行员连接到超级汇点再跑一遍最大流就得了...
过于蒟蒻的我居然脑抽一开始觉得超级源点和超级汇点要连容量为INF的边...
好了代码时间
#include <queue>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm> const int MAXE=;
const int MAXV=;
const int INF=0x7FFFFFFF; struct Edge{
int from;
int to;
int flow;
Edge* rev;
Edge* next;
};
Edge E[MAXE];
Edge* head[MAXV];
Edge* top=E; int v,n;
int depth[MAXV]; bool BFS(int,int);
int Dinic(int,int);
int DFS(int,int,int);
void Insert(int,int,int); int main(){
freopen("flyer.in","r",stdin);
freopen("flyer.out","w",stdout);
int a,b;
scanf("%d%d",&v,&n);
while(scanf("%d%d",&a,&b)==){
Insert(a,b,);
}
for(int i=;i<=n;i++){
Insert(,i,);
}
for(int i=n+;i<=v;i++){
Insert(i,v+,);
}
printf("%d\n",Dinic(,v+));
return ;
} int Dinic(int s,int t){
int ans=;
while(BFS(s,t)){
ans+=DFS(s,INF,t);
}
return ans;
} inline void Insert(int a,int b,int f){
top->from=a;
top->to=b;
top->flow=f;
top->rev=top+;
top->next=head[a];
head[a]=top;
top++;
top->from=b;
top->to=a;
top->flow=;
top->rev=top-;
top->next=head[b];
head[b]=top;
top++;
} bool BFS(int s,int t){
std::queue<int> q;
memset(depth,,sizeof(depth));
depth[s]=;
q.push(s);
while(!q.empty()){
int top=q.front();
q.pop();
for(Edge* i=head[top];i!=NULL;i=i->next){
if(depth[i->to]==&&i->flow!=){
q.push(i->to);
depth[i->to]=depth[top]+;
if(i->to==t)
return true;
}
}
}
return false;
} int DFS(int root,int flow,int t){
if(root==t||flow==)
return flow;
int tmp=flow;
int k;
for(Edge* i=head[root];i!=NULL;i=i->next){
if(i->flow!=&&tmp!=&&depth[i->to]==depth[root]+){
k=DFS(i->to,std::min(tmp,i->flow),t);
if(k==){
depth[i->to]=;
continue;
}
i->flow-=k;
i->rev->flow+=k;
tmp-=k;
if(tmp==)
break;
}
}
return flow-tmp;
}
Backup
以及图包w