[网络流24题] 搭配飞行员

发表于   |  

二分图匹配模板题

问题描述

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

假设有10个驾驶员，其中V1, V2, V3, V4, V5是正驾驶员，V6, V7, V8, V9 , V10是副驾驶员。如果一个正驾驶员和一个副驾驶员可以同机飞行，就在代表他们两个之间连一条线,两个人不能同机飞行，就不连。例如V1和V7可以同机飞行，而V1和V8就不行。请搭配飞行员，使出航的飞机最多。注意:因为驾驶工作分工严格,两个正驾驶员或两个副驾驶员都不能同机飞行.

输入格式

输入文件有若干行
第一行，两个整数n与n1，表示共有n个飞行员(2<=n<=100),其中有n1名飞行员是正驾驶员.
下面有若干行,每行有2个数字a,b。表示正驾驶员a和副驾驶员b可以同机飞行。
注:正驾驶员的编号在前,即正驾驶员的编号小于副驾驶员的编号.

输出格式

输出文件有一行
第一行，1个整数，表示最大起飞的飞机数。

输入输出样例

1
2
3
4
5
6
7
8
9
10
11
输入文件名： flyer.in
10 5
1 7
2 6
2 10
3 7
4 8
5 9
 
输出文件名：flyer.out
4

Code

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#define maxn 10001
#define maxm 100001
#define INF 1000000007
using namespace std;
int fir[maxn], e;
struct Edge{
	int v, f, c, nex, link;
} edge[maxm];
int dis[maxn], n, m, S, T;
void addedge(int u, int v, int c, int f, int l){
	edge[++e].v = v;
	edge[e].f = f;
	edge[e].c = c;
	edge[e].link = e + l;
	edge[e].nex = fir[u];
	fir[u] = e;
}
queue <int> q;
bool bfs(){
	memset(dis, -1, sizeof dis);
	q.push(S);
	dis[S] = 0;
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		for (int i = fir[u]; i; i = edge[i].nex) {
			int v = edge[i].v;
			if (edge[i].f && dis[v] == -1){
				dis[v] = dis[u] + 1;
				if (v==T) return true;
				q.push(v);
			}
		}
	}
	return false;
}
int finds(int u, int maxflow = INF){
	int flow;
	if (u == T) return maxflow;
	for (int i = fir[u]; i; i = edge[i].nex){
		int v = edge[i].v;
		if (edge[i].f && dis[v] == dis[u] + 1 && (flow = finds(v, min(maxflow, edge[i].f)))  ){
			edge[i].f -= flow;
			edge[edge[i].link].f += flow;
			return flow;
		}
	}
	return 0;
}
int dinic(){
	int cnt = 0, flow;
	while (bfs()) {
			while (flow = finds(S)) {
			cnt += flow;
		}
	}
	return cnt;
}
int main(){
 freopen(""flyer.in"",""r"",stdin);
 freopen(""flyer.out"",""w"",stdout);
	scanf(""%d%d"", &n, &m);
	int i, j;
	while (scanf(""%d%d"", &i, &j)!=EOF){
		if (i == -1 || j == -1) break;
		addedge(i, j, 1, 1, 1);
		addedge(j, i, 0, 0, -1);
	}
	for (int i = 1; i <= m; i++) {
		addedge(n+2, i, 1, 1, 1);
		addedge(i, n+2, 0, 0, -1);
	}
	for (int i = m+1; i <= n; i++) {
		addedge(i, n+1, 1, 1, 1);
		addedge(n+1, i, 0, 0, -1);
	}
	S = n+2; T = n+1;
	printf(""%d\n"",dinic());
	// for (int u= 1; u <= m; u++){
	// 	for (int i = fir[u]; i; i = edge[i].nex){
	// 		if (edge[i].f == 0 && edge[i].v <= n) {
	// 			printf(""%d %d\n"", u, edge[i].v);
	// 			break;
	// 		}
	// 	}
	// }
}