2006 飞行员配对(二分图最大匹配,匈牙利算法)

题目来源: 网络流24题
基准时间限制:1 秒 空间限制:131072 KB 分值: 0 难度:基础题

第二次世界大战时期,英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的2名飞行员,其中1名是英国飞行员,另1名是外籍飞行员。在众多的飞行员中,每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。如何选择配对飞行的飞行员才能使一次派出最多的飞机。对于给定的外籍飞行员与英国飞行员的配合情况,试设计一个算法找出最佳飞行员配对方案,使皇家空 军一次能派出最多的飞机 。对于给定的外籍飞行员与英国飞行员的配合情况,编程找出一个最佳飞行员配对方案, 使皇家空军一次能派出最多的飞机。

Input

第1行有2个正整数 m 和 n。n 是皇家空军的飞行 员总数(n<100);m 是外籍飞行员数。外籍飞行员编号为 1m;英国飞行员编号为 m+1n。接下来每行有 2 个正整数 i 和 j,表示外籍飞行员 i 可以和英国飞行员 j 配合。输入最后以 2 个-1 结束。

Output

第 1 行是最佳飞行 员配对方案一次能派出的最多的飞机数 M。如果所求的最佳飞行员配对方案不存在,则输出‘No Solution!’。


题解:

裸的匈牙利算法求二分图最大匹配

这篇讲的超级生动形象了https://blog.csdn.net/cillyb/article/details/55511666

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <fstream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <cmath>
#include <list>
#include <vector>
using namespace std;

const int N=105;
vector<int>g[N];
int n,m,ans=0,match[N];
bool vis[N];
bool dfs(int x){
for(int i=0;i<g[x].size();i++){
int v=g[x][i];
if(!vis[v]){
vis[v]=true;//标记已试图匹配
if(match[v]==-1||dfs(match[v])){
//这个点没匹配过或者这个点匹配的可拆
match[v]=x;
return true;
}
}
}
return false;
}
int main(){
scanf("%d%d",&m,&n);
int x,y;
while(scanf("%d%d",&x,&y),x!=-1&&y!=-1){
g[x].push_back(y);
g[y].push_back(x);
}
memset(match,-1,sizeof(match));
for(int i=1;i<=m;i++){
memset(vis,false,sizeof(vis));
if(dfs(i))ans++;
}
printf("%d\n",ans);
return 0;
}
打赏
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • Copyrights © 2018-2020 LeFlacon

奶茶一杯 快乐起飞

支付宝
微信