搭配飞行员

发表于 | 分类于

题目

传送门
飞行大队有若干个来自各地的驾驶员，专门驾驶一种型号的飞机，这种飞机每架有两个驾驶员,需一个正驾驶员和一个副驾驶员。
由于种种原因，例如相互配合的问题，有些驾驶员不能在同一架飞机上飞行，问如何搭配驾驶员才能使出航的飞机最多。
假设有10个驾驶员，V1，V2，…，V10就代表达10个驾驶员,其中V1，V2，V3，V4，V5是正驾驶员,V6，V7，V8，V9，V10是副驾驶员。如果一个正驾驶员和一个副驾驶员可以同机飞行，就在代表他们两个之间连一条线,两个人不能同机飞行，就不连。例如V1和V7可以同机飞行，而V1和V8就不行。请搭配飞行员，使出航的飞机最多。注意:因为驾驶工作分工严格,两个正驾驶员或两个副驾驶员都不能同机飞行.

INPUT

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

OUTPUT

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

SAMPLE

INPUT

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

OUTPUT

4

解题报告

没啥好说的，第一道网络流= =，以前用二分图水的= =，将正驾驶员与源点连边，副驾驶员与汇点连边，可以搭配的正副驾驶员连边，跑最大流即可

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
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
int n,n1,n2;
struct edge{
	int s,e,n,w;
}a[2001];
int pre[101],tot;
inline void insert(int s,int e,int w){
	a[tot].s=s;
	a[tot].e=e;
	a[tot].w=w;
	a[tot].n=pre[s];
	pre[s]=tot++;
}
int x,y;
int sup;
int inf(0x7fffffff);
int adj[101];
int dis[101];
inline bool bfs(int s,int t){
	memset(dis,0,sizeof(dis));
	queue<int>q;
	q.push(s);
	dis[s]=1;
	while(!q.empty()){
		int k(q.front());
		q.pop();
	 	for(int i=pre[k];i!=-1;i=a[i].n){
			if(!a[i].w||dis[a[i].e])
				continue;
			dis[a[i].e]=dis[k]+1;
			if(a[i].e==t)
				return true;
			q.push(a[i].e);
        }
    }
    return false;
}
inline int my_min(int a,int b){
	return a<b?a:b;
}
inline int dfs(int now,int flow){
	if(now==sup)
		return flow;
	int tmp(flow),f;
	for(int i=pre[now];i!=-1;i=a[i].n){
		if(!a[i].w||!tmp||dis[a[i].e]!=dis[now]+1)
			continue;
		f=dfs(a[i].e,my_min(a[i].w,tmp));
		if(!f){
			dis[a[i].e]=0;
			continue;
		}
		a[i].w-=f;
		a[i^1].w+=f;
		tmp-=f;
	}
	return flow-tmp;
}
inline void dinic(int s,int t){
	int ans(0);
	//bfs(s,t);cout<<"j";
	while(bfs(s,t))
		ans+=dfs(s,inf);
	printf("%d",ans);
}
inline int gg(){
	freopen("flyer.in","r",stdin);
	freopen("flyer.out","w",stdout);
	memset(pre,-1,sizeof(pre));
	scanf("%d%d",&n,&n1);
	sup=n+1;
	n2=n-n1;
	while(scanf("%d%d",&x,&y)==2)
		insert(x,y,1),insert(y,x,0);
	for(int i=1;i<=n1;i++)
		insert(0,i,1),insert(i,0,0);
	for(int i=n1+1,j=1;j<=n2;j++,i++)
		insert(i,sup,1),insert(sup,i,0);
	dinic(0,sup);
}
int K(gg());
int main(){;}