「网络流 24 题」搭配飞行员（二分匹配最大匹配）-白红宇

「网络流 24 题」搭配飞行员（二分匹配最大匹配）

阅读量：4980 次

发布时间：2019-06-12

本文共 1308 字，大约阅读时间需要 4 分钟。

题目描述

飞行大队有若干个来自各地的驾驶员，专门驾驶一种型号的飞机，这种飞机每架有两个驾驶员，需一个正驾驶员和一个副驾驶员。由于种种原因，例如相互配合的问题，有些驾驶员不能在同一架飞机上飞行，问如何搭配驾驶员才能使出航的飞机最多。

因为驾驶工作分工严格,两个正驾驶员或两个副驾驶员都不能同机飞行。

输入格式

第一行，两个整数 n n n 与 m m m，表示共有 n n n 个飞行员，其中有 m m m 名飞行员是正驾驶员。
下面有若干行，每行有 2 2 2 个数字 a a a、b b b。表示正驾驶员 a a a 和副驾驶员 b b b 可以同机飞行。
注：正驾驶员的编号在前，即正驾驶员的编号小于副驾驶员的编号。

输出格式

仅一行一个整数，表示最大起飞的飞机数。

样例

样例输入样例输出

10 5 4
1 7
2 6
2 10
3 7
4 8
5 9

题解：二分匹配最大匹配模板。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int maxn = 300;vector
         
          E[maxn];int used[maxn];int match[maxn];int n,m;void add_edge(int u,int v){ E[u].push_back(v); E[v].push_back(u);}bool dfs(int x){ used[x] = 1; for(int i = 0; i < E[x].size(); i ++) { int u = E[x][i]; int v = match[u]; if(v == -1 || used[v] == -1 && dfs(v)) { match[u] = x; match[x] = u; return true; } } return false;}int max_match(){ int res = 0; memset(match,-1,sizeof(match)); for(int i = 1; i <= m; i ++) { if(match[i] == -1) { memset(used,-1,sizeof(used)); if(dfs(i)) res ++; } } return res;}int main(){ scanf("%d %d",&n, &m); int u,v; while(scanf("%d %d",&u,&v)!=EOF) { add_edge(u,v); } int ans = max_match(); printf("%d\n",ans); return 0;}